算法乐园主页笔记刷题

Algorithm-learning-notes

算法笔记+个人代码（菜，仅供参考）

笔记未完成，正在更新

已完成：数组、排序、链表、哈希表、栈和队列、二叉树、回溯、贪心、动态规划

正在更新：图论、字符串、单调栈

版本：2023-08-31

基础算法总结

题目参考：https://www.programmercarl.com/

Algorithm-learning-notes基础算法总结数组1:二分查找数组3:有序数组的平方数组4:长度最小的子数组|滑动窗口排序专题:1插入排序数组的插入排序排序插入排序优化:折半插入排序链表的插入排序2希尔排序3冒泡排序数组的冒泡排序链表的冒泡排序4快速排序5选择排序数组的选择排序:链表的选择排序6堆排序无脑递归版本:(空间复杂度偏高)奇妙循环版本:复杂度分析:(对于循环版本的代码)应用：合并K个升序链表7归并排序复杂度分析对数组归并排序对链表归并排序8基数排序复杂度分析对链表基数排序链表1：移除链表元素链表2:设计链表链表3:反转链表链表4:两两交换链表中的节点链表5:删除链表的倒数第N个节点链表6：相交链表链表7：环形链表II*哈希表1: 有效的字母异位词哈希表2:两个数组的交集哈希表3:快乐数哈希表4:两数之和哈希表5:四数相加II哈希表6:赎金信哈希表6.9:两数之和 II - 输入有序数组哈希表7:三数之和字符串1：反转字符串字符串2:反转字符串II字符串3:替换空格字符串4:反转字符串中的单词字符串6:找出字符串中第一个匹配项的下标字符串7：重复的子字符串字符串8：有效数字方法1：暴力if-else方法2：有限状态自动机方法3：正则表达式字符串9：验证IP地址字符串10：实现Trie(前缀树)字符串11：连接词字符串12：字符流栈和队列4:有效的括号栈和队列5:删除字符串中的所有相邻重复项栈和队列6:逆波兰表达式求值栈和队列7：基本计算器栈和队列8：基本计算器II二叉树2.递归遍历二叉树3.非递归遍历先序遍历:后序遍历:中序遍历:*二叉树5：层序遍历二叉树6：翻转二叉树二叉树8：对称二叉树二叉树9:二叉树的最大深度二叉树10:二叉树的最小深度二叉树11:完全二叉树的节点个数方法1:二分查找+位运算方法2:寻找满二叉树二叉树12:平衡二叉树二叉树13：二叉树的所有路径二叉树15:左叶子之和二叉树16:找树左下角的值二叉树17:路径总和二叉树18:从中序与后序遍历序列构造二叉树, 从前序与中序遍历序列构造二叉树二叉树19:最大二叉树二叉树21:合并二叉树二叉树22:二叉搜索树中的搜索二叉树23:验证二叉搜索树二叉树24:二叉搜索树的最小绝对差二叉树25：二叉搜索树中的众数二叉树26:二叉树的最近公共祖先二叉树28:二叉搜索树的最近公共祖先二叉树29:二叉搜索树的插入操作二叉树30:删除二叉搜索树中的节点回溯2：组合回溯4:组合总和III回溯5:电话号码的字母组合回溯7:组合总和回溯8:组合总和II回溯9：分割回文串回溯10：复原IP地址回溯11：子集回溯13：子集II回溯14：递增子序列回溯15：全排列回溯16：全排列II回溯19：重新安排行程回溯20：N皇后回溯21：解数独贪心2：分发饼干贪心3：摆动序列贪心4：最大子数组和贪心6:买卖股票的最佳时机 II贪心7:跳跃游戏贪心8：跳跃游戏II贪心9:K次取反后最大化的数组和贪心11: 加油站贪心12:分发糖果贪心13:柠檬水找零贪心14：根据身高重建队列*贪心17:用最少数量的箭引爆气球*贪心18:无重叠区间贪心19:划分字母区间贪心20：合并区间贪心22：单调递增的数字贪心23:监控二叉树图论最小生成树:连接所有节点的最小费用prim普里姆算法Kruskal算法最短路径问题:Dijkstra算法Dijkstra算法优化:使用小根堆priority_queueFloyd算法Bellman-ford算法SPFA算法拓扑排序课程表课程表II图论1：统计点对的数目代码随想录的刷题顺序:动态规划3:爬楼梯动态规划4:使用最小花费爬楼梯动态规划6:不同路径动态规划7:不同路径II动态规划8:整数拆分动态规划9:不同的二叉搜索树0-1背包系列 13~17动态规划13:分割等和子集动态规划14：最后一块石头的重量II动态规划16：目标和动态规划17：一和零完全背包系列 19~26动态规划19：零钱兑换II动态规划21：组合总和IV动态规划23：零钱兑换动态规划24：完全平方数动态规划26：单词拆分打家劫舍问题29-31动态规划29：打家劫舍动态规划30：打家劫舍II动态规划31：打家劫舍III股票问题32-38动态规划32.买卖股票的最佳时机动态规划34.买卖股票的最佳时机II动态规划35.买卖股票的最佳时机III动态规划36：买卖股票的最佳时机IV动态规划37：买卖股票的最佳时机含冷冻期动态规划38：买卖股票的最佳时机含手续费子序列问题动态规划41：最长递增子序列动态规划42：最长连续递增序列动态规划43：最长公共子序列动态规划44：最长公共子序列动态规划45：不相交的线动态规划46：最大子序和动态规划47：判断子序列动态规划48：不同的子序列动态规划49：两个字符串的删除操作动态规划50：编辑距离动态规划52：回文子串动态规划53：最长回文子序列动态规划54：切披萨的方案数灵神的刷题顺序:动态规划:从记忆化搜索到递推198打家劫舍70. 爬楼梯746. 使用最小花费爬楼梯2466.统计构造好字符串的方案数213.打家劫舍 II拆分类动态规划343.整数拆分96.不同的二叉搜索树0-1背包和完全背包494. 目标和(0-1背包)解法1. 回溯(暴力)解法:可以1952ms踩线通过解法2:灵神的0-1背包记忆递归模板记忆递归模板解题解法3: 数组递推的动态规划解法322. 零钱兑换416. 分割等和子集1049.最后一块石头的重量II279. 完全平方数518. 零钱兑换 II377.组合总和IV474. 一和零879.盈利计划最长公共子序列1143.最长公共子序列72. 编辑距离583. 两个字符串的删除操作712. 两个字符串的最小ASCII删除和1458. 两个子序列的最大点积97. 交错字符串单调栈1：每日温度单调栈2：下一个更大元素I

数组1:二分查找

手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找(参考视频)

leetcode704

左闭右闭模板:

注意四个细节:

right=len-1
left<=right
right=mid-1
left=mid+1

C++


1
class Solution {
2
public:
3
    int search(vector<int>& nums, int target) 
4
    {
5
        int len=nums.size();
6
        int left=0;
7
        int right=len-1;
8
        while(left<=right)//左闭右闭
9
        {
10
            int mid=(left+right)/2;
11
            if(nums[mid]==target)
12
                return mid;
13
            else if(nums[mid]>target)
14
                right=mid-1;
15
            else 
16
                left=mid+1;
17
        }
18
        return -1;
19
    }
20
};

python:


xxxxxxxxxx
13
1
class Solution:
2
    def search(self, nums: List[int], target: int) -> int:
3
        left=0
4
        right=len(nums)-1
5
        while left<=right:  # 左闭右闭
6
            mid=(left+right)//2
7
            if nums[mid]==target:
8
                return mid
9
            elif nums[mid]>target:
10
                right=mid-1
11
            else:
12
                left=mid+1
13
        return -1

左闭右开模板:

注意四个细节:

right=nums.size()
left<right
left=mid+1
right=mid

C++:


xxxxxxxxxx
19
1
class Solution {
2
public:
3
    int search(vector<int>& nums, int target) 
4
    {
5
        int left=0;
6
        int right=nums.size();
7
        while(left<right) //左闭右开
8
        {
9
            int mid=(left+right)/2;
10
            if(nums[mid]==target)
11
                return mid;
12
            else if(nums[mid]<target)
13
                left=mid+1;
14
            else
15
                right=mid;
16
        }
17
        return -1;
18
    }
19
};

python:


x
1
class Solution:
2
    def search(self, nums: List[int], target: int) -> int:
3
        left=0
4
        right=len(nums)
5
        while left<right:  # 左闭右开
6
            mid=(left+right)//2
7
            if nums[mid]==target:
8
                return mid
9
            elif nums[mid]<target:
10
                left=mid+1
11
            else:
12
                right=mid
13
        return -1
14

数组3:有序数组的平方

双指针法经典题目 | LeetCode：977.有序数组的平方(参考视频)

leetcode977

推荐双指针法,由绝对值最小的数开始往两边遍历

当然也可以由两边向中间遍历数组

python:


xxxxxxxxxx
27
1
class Solution:
2
    def sortedSquares(self, nums: List[int]) -> List[int]:
3
        le=len(nums)
4
        idx=0
5
        for idx in range(le):
6
            if idx+1<le and abs(nums[idx+1])>abs(nums[idx]):
7
                break
8
        left=idx-1
9
        right=idx+1
10
        arr=[nums[idx]**2]
11
        while 1:
12
            if left>=0 and right<le:
13
                if abs(nums[left])<abs(nums[right]):
14
                    arr.append(nums[left]**2)
15
                    left-=1
16
                else: 
17
                    arr.append(nums[right]**2)
18
                    right+=1
19
            elif left>=0:
20
                arr.append(nums[left]**2)
21
                left-=1
22
            elif right<le:
23
                arr.append(nums[right]**2)
24
                right+=1
25
            else:
26
                break
27
        return arr

数组4:长度最小的子数组|滑动窗口

leetcode209

拿下滑动窗口！ | LeetCode 209 长度最小的子数(参考视频)

python:


xxxxxxxxxx
21
1
class Solution:
2
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
3
        le=len(nums)
4
        left=add=0
5
        right=-1
6
        ret=inf
7
        while right+1<le:
8
            while add<=target and right+1<le:
9
                right+=1
10
                add+=nums[right]
11
                if add>=target:
12
                    ret=min(ret,right-left+1)
13
            while add>target:
14
                add-=nums[left]
15
                left+=1
16
                if add>=target:
17
                    ret=min(ret,right-left+1)
18
        if ret==inf:
19
            return 0
20
        else :
21
            return ret

排序专题:

数组排序:leetcode912

单链表排序:leetcode148(测试用例很容易超时,matrix的面试题,当年我就没做出来😖)

对链表进行插入排序:leetcode147(不容易超时)

1插入排序

支持数组和链表

数组的插入排序排序

$O(1)$ ,因为只使用了常数个临时变量

$O(n)$ ,对应于数组已经有序的情况

$O(n^2)$ ,对应数组完全逆序的情况

$O(n^2)$

具有稳定性


xxxxxxxxxx
19
1
class Solution {
2
public:
3
    vector<int> sortArray(vector<int>& nums) //插入排序
4
    {
5
        int n=nums.size();//数组长度
6
        for(int i=1;i<n;++i)
7
        {
8
            if(nums[i-1]>nums[i])
9
            {
10
                int tmp=nums[i];//取出当前遍历的元素
11
                int j=i-1;
12
                for(;j>=0&&nums[j]>tmp;--j)//向左遍历，直到遍历到小于或等于tmp的元素
13
                    nums[j+1]=nums[j];//将比tmp大的元素右移一格
14
                nums[j+1]=tmp;//将tmp插入新的位置
15
            }
16
        }
17
        return nums;
18
    }
19
};

(在leetcode912提交会超时.leetcode147通过)

插入排序优化:折半插入排序

当遍历到第i个1元素时,[0,i-1]的所有元素时有序的,可以利用二分查找的方法找到插入位置

然鹅, 时间复杂度没有质的飞跃

$O(1)$

$O(n)$ ,对应于数组已经有序的情况

$O(n^2)$ ,对应数组完全逆序的情况

$O(n^2)$

具有稳定性


xxxxxxxxxx
28
1
class Solution {
2
public:
3
    vector<int> sortArray(vector<int>& nums) //插入排序
4
    {
5
        int n=nums.size();//数组长度
6
        for(int i=1;i<n;++i)
7
        {
8
            if(nums[i-1]>nums[i])
9
            {
10
                int left=0,right=i-1;
11
                while(left<=right)//二分查找
12
                {
13
                    int mid=(left+right)/2;
14
                    if(nums[i]>=nums[mid])//这里取等是为了算法的稳定性
15
                        left=mid+1;
16
                    else 
17
                        right=mid-1;
18
                }
19
                //将[left,i-1]的所有元素右移
20
                int tmp=nums[i];
21
                for(int j=i-1;j>=left;--j)
22
                    nums[j+1]=nums[j];
23
                nums[left]=tmp;
24
            }
25
        }
26
        return nums;
27
    }
28
};

(在leetcode912提交会超时)

链表的插入排序

$O(1)$ ,只额外开辟了常数级别的空间

$O(n)$ ,对应于数组已经有序的情况

$O(n^2)$ ,对应数组完全逆序的情况

$O(n^2)$

具有稳定性


xxxxxxxxxx
28
1
class Solution {//插入排序
2
public:
3
    ListNode* sortList(ListNode* head) 
4
    {
5
        if(head==nullptr)//保证链表长度≥1
6
            return head;
7
        ListNode* dummyhead=new ListNode(0,head);
8
        ListNode* i=head;
9
        while(i->next!=nullptr)
10
        {
11
            if(i->val>i->next->val)
12
            {
13
                ListNode* tmp=i->next;//取出当前节点
14
                i->next=tmp->next;//将当前节点从链表删除
15
                ListNode* j=dummyhead;
16
                while(j->next->val<=tmp->val)
17
                    j=j->next;
18
                tmp->next=j->next;
19
                j->next=tmp;//将当前tmp节点插入链表
20
            }
21
            else
22
                i=i->next;
23
        }
24
        ListNode* ret=dummyhead->next;
25
        delete dummyhead;
26
        return ret;
27
    }
28
};

(在leetcode148提交会超时,leetcode147提交通过,16ms,9.3MB)

2希尔排序

仅支持数组,不适用链表

先追求表中元素部分有序,再逐渐逼近全局有序

每一轮都按照一个给定的间隔进行插入排序,这个间隔应当逐渐减少,最后必须为1

$\frac n 2$ $\frac 1 2$ ,直到变为1

$O(1)$

$d_1,d_2,d_3,\cdots$ 的选择有关,目前无法用数学手段证明确切的时间复杂度

$O(n^2)$ $d=1$ 的时候,这时候希尔排序退化为插入排序

$n$ $O(n^{1.3})$

不具有稳定性,例如:

原始序列: 65 49 49

第一趟:d=2 49 49 65

第一趟:d=1 49 49 65


xxxxxxxxxx
22
1
class Solution {
2
public:
3
    vector<int> sortArray(vector<int>& nums) //希尔排序
4
    {
5
        int n=nums.size();//数组长度
6
        for(int d=n/2;d>=1;d/=2)//步长变化
7
        {
8
            for(int i=d;i<n;++i)
9
            {
10
                if(nums[i-d]>nums[i])
11
                {
12
                    int tmp=nums[i];
13
                    int j=i-d;
14
                    for(;j>=0&&nums[j]>tmp;j-=d)
15
                        nums[j+d]=nums[j];
16
                    nums[j+d]=tmp;
17
                }
18
            }
19
        }
20
        return nums;
21
    }
22
};

(在leetcode912提交通过,224ms,65MB)

3冒泡排序

数组的冒泡排序

可用于数组和链表

$O(1)$

时间复杂度

$O(n)$

$O(n^2)$

具有稳定性


xxxxxxxxxx
23
1
class Solution {
2
public:
3
    vector<int> sortArray(vector<int>& nums) //冒泡排序
4
    {
5
        int n=nums.size();//数组长度
6
        //每一轮都把最小的元素移动到前面
7
        for(int i=0;i<n-1;++i)
8
        {
9
            int flag=0;//本趟冒泡是否发生交换的标志
10
            for(int j=n-2;j>=i;--j)//一趟冒泡
11
            {
12
                if(nums[j]>nums[j+1])//如果逆序
13
                {
14
                    flag=1;
15
                    swap(nums[j],nums[j+1]);//交换
16
                }
17
            }
18
            if(flag==0)//本趟遍历没有交换，当前数组已经有序，不需要继续循环
19
                break;
20
        }
21
        return nums;
22
    }
23
};

(在leetcode912提交会超时)

链表的冒泡排序


xxxxxxxxxx
41
1
#define INT_MAX 0x7fffffff
2
class Solution {//冒泡排序
3
public:
4
    ListNode* sortList(ListNode* head) 
5
    {
6
        if(head==nullptr||head->next==nullptr)//保证链表长度>1
7
            return head;
8
        ListNode* dummyhead=new ListNode(0,head);//虚拟头节点
9
        int cur_max=INT_MAX;
10
        ListNode* pre=dummyhead,*left=head,*right=head->next;
11
        while(right!=nullptr&&right->val<=cur_max)
12
        {
13
            int flag=0;
14
            while(right!=nullptr&&right->val<=cur_max)
15
            {
16
                if(left->val>right->val)
17
                {
18
                    left->next=right->next;
19
                    right->next=left;
20
                    pre->next=right;
21
                    pre=right;
22
                    right=left->next;
23
                    flag=1;
24
                }
25
                else
26
                {
27
                    pre=left;
28
                    left=right;
29
                    right=right->next;
30
                }
31
            }
32
            cur_max=left->val;
33
            pre=dummyhead,left=dummyhead->next,right=left->next;
34
            if(flag==0)
35
                break;
36
        }
37
        ListNode* ret=dummyhead->next;
38
        delete dummyhead;
39
        return ret;
40
    }
41
};

(在leetcode148提交会超时,leetcode147通过112ms,9.3MB)

4快速排序

$O(\log_2n)$

$O(n)$

$O(n\log_2n)$

$O(n^2)$

$O(n\log_2n)$

如果每次选中的枢轴将待排序序列划分为均匀的两个部分,则递归深度最小,算法效率最高

若数组原本就有序或逆序,则快速排序性能最差

算法不稳定


xxxxxxxxxx
28
1
class Solution {
2
public:
3
    vector<int> sortArray(vector<int>& nums)//快速排序
4
    {
5
        int n=nums.size();
6
        function<void(int,int)>quick_sort=[&](int low,int high)
7
        {
8
            if(low>=high)
9
                return;
10
            int left=low,right=high;
11
            int pivot=nums[low];
12
            while(low<high)
13
            {
14
                while(low<high&&nums[high]>=pivot)
15
                    --high;
16
                nums[low]=nums[high];
17
                while(low<high&&nums[low]<=pivot)
18
                    ++low;
19
                nums[high]=nums[low];
20
            }
21
            nums[low]=pivot;
22
            quick_sort(left,low-1);
23
            quick_sort(low+1,right);
24
        };
25
        quick_sort(0,n-1);
26
        return nums;
27
    }
28
};

(在leetcode912提交会超时)

5选择排序

数组的选择排序:

$O(1)$

$O(n^2)$

不稳定,例如:主要原因是使用了swap函数,如果牺牲一些时间,整体后移所有元素以避免使用swap,算法可以变为稳定的

原始序列 3 3 1

排序后 1 3 3


xxxxxxxxxx
22
1
class Solution {
2
public:
3
    vector<int> sortArray(vector<int>& nums)//快速排序
4
    {
5
        int n=nums.size();
6
        for(int i=0;i<n-1;++i)
7
        {
8
            int cur_min=INT_MAX;
9
            int min_idx=i;
10
            for(int j=i;j<n;++j)
11
            {
12
                if(nums[j]<cur_min)
13
                {
14
                    cur_min=nums[j];
15
                    min_idx=j;
16
                }
17
            }
18
            swap(nums[i],nums[min_idx]);
19
        }
20
        return nums;
21
    }
22
};

(在leetcode912提交会超时)

链表的选择排序

$O(1)$

$O(n^2)$

具有稳定性


xxxxxxxxxx
36
1
class Solution {
2
public:
3
    ListNode* sortList(ListNode* head) //选择排序
4
    {
5
        ListNode* dummyhead=new ListNode(0,head);//虚拟头节点
6
        ListNode* i=dummyhead,*j=dummyhead;
7
        while(i->next!=nullptr)
8
        {
9
            j=i;
10
            int cur_min=INT_MAX;
11
            ListNode* min_node=i;
12
            while(j->next!=nullptr)
13
            {
14
                if(j->next->val<cur_min)
15
                {
16
                    cur_min=j->next->val;
17
                    min_node=j;
18
                }
19
                j=j->next;
20
            }
21
            if(min_node==i)
22
                i=i->next;
23
            else
24
            {
25
                ListNode* tmp=min_node->next;
26
                min_node->next=tmp->next;
27
                tmp->next=i->next;
28
                i->next=tmp;
29
                i=tmp;
30
            }
31
        }
32
        ListNode* ret=dummyhead->next;
33
        delete dummyhead;
34
        return ret;
35
    }
36
};

(在leetcode148提交会超时,leetcode147通过,80ms,9.4MB)

6堆排序

只适用于数组

堆排序利用大根堆,本质是按照节点序号(从1开始)存储在数组中的完全二叉树

几个基本操作

$2i$
$2i+1$
$\lfloor\frac i 2\rfloor$
$\lceil \log_2(i+1)\rceil$ $\lfloor\log_2i\rfloor+1$

若完全二叉树中有n个节点,则

$2i\le n$
$2i+1\le n$
$i>\lfloor\frac n 2\rfloor$

$L[1...n]$ 满足下面某一条性质,则称为堆(Heap)

$L[i]\ge L[2i]$ $L[i]\ge L[2i+1]$ $1\le i\le\frac n2$ ) 大根堆
$L[i]\le L[2i]$ $L[i]\le L[2i+1]$ $1\le i\le\frac n2$ ) 小根堆

如果下标从0开始,则:

$2i+1$
$2i+2$
$\lfloor\frac {i-1} 2\rfloor$
$\lfloor\log_2(i+1)\rfloor+1$
$0\le i\le\lfloor\frac n2\rfloor-1$

无脑递归版本:(空间复杂度偏高)


xxxxxxxxxx
48
1
class Solution {
2
public:
3
    vector<int> sortArray(vector<int>& nums)//堆排序
4
    {
5
        int n=nums.size();
6
        function<void(int)>recur=[&](int idx)
7
        {
8
            if(2*idx+1>=n)//没有子树
9
                return;
10
            else if(2*idx+2>=n)//只有左子树
11
            {
12
                if(nums[2*idx+1]>nums[idx])
13
                {
14
                    swap(nums[2*idx+1],nums[idx]);
15
                    recur(2*idx+1);
16
                }
17
            }
18
            else//有左右子树
19
            {
20
                if(nums[2*idx+1]>nums[2*idx+2])//左子树更大
21
                {
22
                    if(nums[2*idx+1]>nums[idx])
23
                    {
24
                        swap(nums[2*idx+1],nums[idx]);
25
                        recur(2*idx+1);
26
                    }
27
                }
28
                else//右子树更大
29
                {
30
                    if(nums[2*idx+2]>nums[idx])
31
                    {
32
                        swap(nums[2*idx+2],nums[idx]);
33
                        recur(2*idx+2);
34
                    }
35
                }
36
            }
37
        };
38
        for(int i=n/2-1;i>=0;--i)//构造大根堆
39
            recur(i);
40
        while(n>=2)
41
        {
42
            --n;
43
            swap(nums[n],nums[0]);
44
            recur(0);
45
        }
46
        return nums;
47
    }
48
};

leetcode912通过,308ms,65MB

奇妙循环版本:


xxxxxxxxxx
29
1
class Solution {
2
public:
3
    vector<int> sortArray(vector<int>& nums)//堆排序(非递归版本)
4
    {
5
        int n=nums.size();
6
        function<void(int,int)>head_adjust=[&](int idx,int len)
7
        {
8
            int k=2*idx+1;//idx对应的左孩子的下标
9
            while(k<len)//idx的左孩子存在
10
            {
11
                if(k+1<len&&nums[k]<nums[k+1])//idx的右孩子存在且值大于左孩子
12
                    ++k;//调整k,保证k指向左右孩子中的最大者
13
                if(nums[idx]>=nums[k])
14
                    break;//idx节点最大，结束循环
15
                swap(nums[idx],nums[k]);
16
                idx=k;//以当前孩子为父节点，继续向下检查
17
                k=2*idx+1;//指向当前孩子的左孩子的下标                
18
            }
19
        };
20
        for(int i=n/2-1;i>=0;--i)//构造大根堆
21
            head_adjust(i,n);
22
        for(int i=n-1;i>=1;--i)
23
        {
24
            swap(nums[0],nums[i]);
25
            head_adjust(0,i);
26
        }
27
        return nums;
28
    }
29
};

leetcode912通过,204ms,65MB

复杂度分析:(对于循环版本的代码)

复杂度分析部分考虑下标从1开始

$h=\lfloor\log_2n\rfloor+1$

$i$ $2^{i-1}$ 个节点,只有第1~(h-1)层的节点才可能需要下坠处理,每次下坠最多对比2次,第i层节点下坠最多对比h-i次

把整棵树调整为大根堆, 关键字对比次数:

\begin{aligned} \sum_{i = h - 1}^{1} 2^{i - 1} 2 (h - i) & = \sum_{i = h - 1}^{1} 2^{i} (h - i) \\ = \sum_{j = 1}^{h - 1} 2^{h - j} j \\ = 2^{h} \sum_{j = 1}^{h - 1} \frac{j}{2^{j}} \\ = 2^{⌊ \log_{2} n ⌋ + 1} \cdot (2 - \frac{h + 1}{2^{h - 1}}) \\ \leq 2 n \cdot 2 \\ = 4 n \end{aligned}

$O(n)$

$O(n\log_2n)$

$O(1)$

堆排序不稳定,例如

原始序列 1 2 2

排序后 1 2 2

应用：合并K个升序链表

leetcode23

利用小根堆的性质解决

C++:


xxxxxxxxxx
60
1
#define ninf 20000
2
class Solution {
3
public:
4
    ListNode* mergeKLists(vector<ListNode*>& lists) 
5
    {
6
        ListNode* dummyhead=new ListNode(0,nullptr);//虚拟头节点
7
        ListNode* p=dummyhead;
8
        int n=lists.size();
9
        if(n==0)
10
            return nullptr;
11
        //将lists构造为一个小根堆(按照链表中第一个元素的大小排序)
12
        function<void(int)>recur=[&](int idx)
13
        {
14
            if(idx>n/2-1)//没有孩子
15
                return;
16
            int fa,le,ri;//分别是父节点、左节点、右节点，得到它们的权值用于排序
17
            if(lists[idx]==nullptr)
18
                fa=ninf;
19
            else
20
                fa=lists[idx]->val;
21
            if(2*idx+1>=n||lists[2*idx+1]==nullptr)
22
                le=ninf;
23
            else
24
                le=lists[2*idx+1]->val;
25
            if(2*idx+2>=n||lists[2*idx+2]==nullptr)
26
                ri=ninf;
27
            else
28
                ri=lists[2*idx+2]->val;
29
            if(le<ri)
30
            {
31
                if(le<fa)
32
                {
33
                    swap(lists[2*idx+1],lists[idx]);
34
                    recur(2*idx+1);
35
                }
36
            }
37
            else
38
            {
39
                if(ri<fa)
40
                {
41
                    swap(lists[2*idx+2],lists[idx]);
42
                    recur(2*idx+2);
43
                }
44
            }
45
        };//用于构造和维护小根堆的递归函数
46
        for(int i=n/2-1;i>=0;--i)
47
            recur(i);
48
        while(lists[0]!=nullptr)
49
        {
50
            p->next=lists[0];
51
            p=p->next;
52
            lists[0]=p->next;
53
            p->next=nullptr;
54
            recur(0);
55
        }
56
        ListNode* ret=dummyhead->next;
57
        delete dummyhead;
58
        return ret;
59
    }
60
};

7归并排序

复杂度分析

2路归并的归并树,形态上就是一棵倒立的二叉树

$2^{h-1}$ $n\le 2^{h-1}$

$h-1=\lceil\log_2n\rceil$

$\lceil\log_2n\rceil$

$O(n)$ $O(n\log_2n)$

$O(\log_2n)$ $O(n)$

$O(n)$

归并排序具有稳定性

对数组归并排序


xxxxxxxxxx
39
1
class Solution {
2
public:
3
    vector<int> sortArray(vector<int>& nums)//归并排序
4
    {
5
        int n=nums.size();
6
        vector<int>tmp(n);
7
        function<void(int,int)>merge_sort=[&](int left,int right)
8
        {
9
            if(left>=right)
10
                return;
11
            int mid=(left+right)/2;
12
            merge_sort(left,mid);
13
            merge_sort(mid+1,right);
14
            for(int i=left;i<=right;++i)//将[left,right]的元素临时移动到tmp数组
15
                tmp[i]=nums[i];
16
            int i=left,j=mid+1,k=left;
17
            while(i<=mid&&j<=right)
18
            {
19
                if(tmp[i]<=tmp[j])
20
                {
21
                    nums[k]=tmp[i];
22
                    ++i;
23
                }
24
                else
25
                {
26
                    nums[k]=tmp[j];
27
                    ++j;
28
                }
29
                ++k;
30
            }
31
            for(;i<=mid;++i,++k)
32
                nums[k]=tmp[i];
33
            for(;j<=right;++j,++k)
34
                nums[k]=tmp[j];
35
        };
36
        merge_sort(0,n-1);
37
        return nums;
38
    }
39
};

leetcode912通过,312ms,67.1MB

对链表归并排序


xxxxxxxxxx
72
1
class Solution {
2
public:
3
    ListNode* sortList(ListNode* head) 
4
    {
5
        ListNode* dummyhead=new ListNode(0,head);//虚拟头节点
6
        function<void(ListNode*,ListNode*&)>merge_sort=[&](ListNode* left,ListNode*& right)//左开右闭区间
7
        {
8
            if(left==right||left->next==right)
9
                return;
10
            ListNode* mid=left, * fast=left;//采用快慢指针法找到链表的中点
11
            while(fast->next!=right)
12
            {
13
                fast=fast->next;
14
                mid=mid->next;
15
                if(fast->next==right)
16
                    break;
17
                fast=fast->next;
18
            }
19
            merge_sort(left,mid);
20
            merge_sort(mid,right);
21
            ListNode* ld=new ListNode(0,left->next),*rd=new ListNode(0,mid->next),*end=right->next;
22
            ListNode* p=left;
23
            mid->next=nullptr;
24
            right->next=nullptr;
25
            left->next=end;
26
            while(ld->next!=nullptr&&rd->next!=nullptr)
27
            {
28
                ListNode* tmp;
29
                if(ld->next->val<=rd->next->val)
30
                {
31
                    tmp=ld->next;
32
                    ld->next=tmp->next;
33
                }
34
                else
35
                {
36
                    tmp=rd->next;
37
                    rd->next=tmp->next;
38
                }
39
                tmp->next=p->next;
40
                p->next=tmp;
41
                p=tmp;
42
            }
43
            while(ld->next!=nullptr)
44
            {
45
                ListNode* tmp;
46
                tmp=ld->next;
47
                ld->next=tmp->next;
48
                tmp->next=p->next;
49
                p->next=tmp;
50
                p=tmp;
51
            }
52
            while(rd->next!=nullptr)
53
            {
54
                ListNode* tmp;
55
                tmp=rd->next;
56
                rd->next=tmp->next;
57
                tmp->next=p->next;
58
                p->next=tmp;
59
                p=tmp;
60
            }
61
            right=p;
62
            delete ld,rd;
63
        };
64
        ListNode* p=dummyhead;
65
        while(p->next!=nullptr)
66
            p=p->next;
67
        merge_sort(dummyhead,p);
68
        ListNode* ret=dummyhead->next;
69
        delete dummyhead;
70
        return ret;
71
    }
72
};

leetcode148通过,368ms,95.18MB

8基数排序

复杂度分析

$a_j$ $(k_j^{d-1},k_j^{d-2},k_j^{d-3},\cdots,k_j^{1},k_j^{0})$ 组成

$0\le k_j^{i}\le r-1\quad (0\le j<n,0\le i\le d-1)$ ,r称为基数

$O(n)$

$O(n)$ $O(r)$ $O(d(n+r))$

$-10^5 \le Node.val \le 10^5$ $n\in[0,5\times10^4]$

$10^5$ ,保证所有数为正数,对于十进制数r=10,d不超过6

$O(n)$ $O(n)$

基数排序是稳定的, ~~因为基你太稳~~

对链表基数排序


xxxxxxxxxx
47
1
class Solution {
2
public:
3
    ListNode* sortList(ListNode* head)//基数排序
4
    {
5
        ListNode* dummyhead=new ListNode(0,head);
6
        ListNode* p=dummyhead;
7
        while(p->next!=nullptr)
8
        {
9
            p->next->val+=100000;
10
            p=p->next;
11
        }
12
        vector<queue<ListNode*>>vec(10);
13
        for(int i=1;i<=100000;i*=10)
14
        {
15
            int flag=0;
16
            while(dummyhead->next!=nullptr)
17
            {
18
                if(dummyhead->next->val/(i*10)!=0)
19
                    flag=1;
20
                vec[dummyhead->next->val/i%10].push(dummyhead->next);
21
                dummyhead->next=dummyhead->next->next;
22
            }
23
            ListNode* p=dummyhead;
24
            for(int j=0;j<10;++j)
25
            {
26
                while(!vec[j].empty())
27
                {
28
                    vec[j].front()->next=p->next;
29
                    p->next=vec[j].front();
30
                    p=p->next;
31
                    vec[j].pop();
32
                }
33
            }
34
            if(flag==0)
35
                break;
36
        }
37
        p=dummyhead;
38
        while(p->next!=nullptr)
39
        {
40
            p->next->val-=100000;
41
            p=p->next;
42
        }
43
        ListNode* ret=dummyhead->next;
44
        delete dummyhead;
45
        return ret;
46
    }
47
};

leetcode148通过,216ms,63.4MB

链表1：移除链表元素

leetcode203

使用虚拟头节点:

C++


xxxxxxxxxx
36
1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode() : val(0), next(nullptr) {}
7
 *     ListNode(int x) : val(x), next(nullptr) {}
8
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9
 * };
10
 */
11
class Solution {
12
public:
13
    ListNode* removeElements(ListNode* head, int val)
14
    {
15
        ListNode* dummyhead=new ListNode(-1,head);
16
        ListNode* pre=dummyhead;
17
        ListNode* cur=head;
18
        while(cur!=nullptr)
19
        {
20
            if(cur->val==val)
21
            {
22
                pre->next=cur->next;
23
                delete cur;
24
                cur=pre->next;
25
            }
26
            else
27
            {
28
                pre=pre->next;
29
                cur=cur->next;
30
            }
31
        }
32
        head=dummyhead->next;
33
        delete dummyhead;
34
        return head;
35
    }
36
};

不使用虚拟头节点:

python


xxxxxxxxxx
16
1
# Definition for singly-linked list.
2
# class ListNode:
3
#     def __init__(self, val=0, next=None):
4
#         self.val = val
5
#         self.next = next
6
class Solution:
7
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
8
        while head!=None and head.val==val:
9
            head=head.next
10
        p=head
11
        while p!=None and p.next!=None:
12
            if p.next.val==val:
13
                p.next=p.next.next
14
            else:
15
                p=p.next
16
        return head

链表2:设计链表

leetcode707

单向链表(使用虚拟头节点):


xxxxxxxxxx
92
1
// struct ListNode 
2
// {
3
//     int val;
4
//     ListNode *next;
5
//     ListNode() : val(0), next(nullptr) {}
6
//     ListNode(int x) : val(x), next(nullptr) {}
7
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
8
// };
9
class MyLinkedList {
10
public:
11
    ListNode* root;
12
    MyLinkedList() 
13
    {
14
        root=new ListNode;
15
    }  
16
    int get(int index) 
17
    {
18
        if(index<0)
19
            return -1;
20
        ListNode* p=root;
21
        int i=-1;
22
        while(i<index&&p->next!=nullptr)
23
        {
24
            p=p->next;
25
            ++i;
26
        }
27
        if(i<index)
28
            return -1;
29
        else
30
            return p->val;
31
    }
32
    
33
    void addAtHead(int val) 
34
    {
35
        ListNode* add=new ListNode(val,root->next);
36
        root->next=add;
37
    }
38
    
39
    void addAtTail(int val) 
40
    {
41
        ListNode* p=root;
42
        while(p->next!=nullptr)
43
            p=p->next;
44
        p->next=new ListNode(val);
45
    }
46
    
47
    void addAtIndex(int index, int val) 
48
    {
49
        if(index<0)
50
            return;
51
        --index;
52
        ListNode* p=root;
53
        int i=-1;
54
        while(i<index&&p->next!=nullptr)
55
        {
56
            p=p->next;
57
            ++i;
58
        }
59
        if(i<index)
60
            return;
61
        else
62
        {
63
            ListNode* add=new ListNode(val,p->next);
64
            p->next=add;
65
        }
66
    }
67
    void deleteAtIndex(int index) 
68
    {
69
        if(index<0)
70
            return;
71
        --index;
72
        ListNode* p=root;
73
        int i=-1;
74
        while(i<index&&p->next!=nullptr)
75
        {
76
            p=p->next;
77
            ++i;
78
        }
79
        if(i<index)
80
            return;
81
        else
82
        {
83
            if(p->next!=nullptr)
84
            {
85
                ListNode* rubbish=p->next;
86
                p->next=p->next->next;
87
                delete rubbish;
88
            }
89
        }
90

91
    }
92
};

链表3:反转链表

leetcode206

方法1:栈

$O(n)$ $O(n)$


xxxxxxxxxx
25
1
class Solution {
2
public:
3
    ListNode* reverseList(ListNode* head) 
4
    {
5
        if(head==nullptr)
6
            return head;
7
        stack<ListNode*>sta;
8
        while(head!=nullptr)
9
        {
10
            sta.push(head);
11
            head=head->next;
12
        }
13
        head=sta.top();
14
        sta.pop();
15
        ListNode* p=head;
16
        while(!sta.empty())
17
        {
18
            p->next=sta.top();
19
            p=p->next;
20
            sta.pop();
21
        }
22
        p->next=nullptr;
23
        return head;
24
    }
25
};

方法2:双指针

$O(n)$ $O(1)$


xxxxxxxxxx
15
1
class Solution {
2
public:
3
    ListNode* reverseList(ListNode* head) 
4
    {
5
        ListNode* pre=nullptr,*cur=head;
6
        while(cur!=nullptr)
7
        {
8
            ListNode* tmp=cur->next;
9
            cur->next=pre;
10
            pre=cur;
11
            cur=tmp;
12
        }
13
        return pre;
14
    }
15
};

方法3:递归

$O(n)$ $O(n)$


xxxxxxxxxx
16
1
class Solution {
2
public:
3
    ListNode* reverseList(ListNode* head) 
4
    {
5
        ListNode* pre=nullptr,*cur=head;
6
        function<ListNode*(ListNode*,ListNode*)>recursion=[&](ListNode* cur,ListNode* pre)
7
        {
8
            if(cur==nullptr)    
9
                return pre;
10
            ListNode* tmp=cur->next;
11
            cur->next=pre;
12
            return recursion(tmp,cur);
13
        };
14
        return recursion(head,nullptr);
15
    }
16
};

链表4:两两交换链表中的节点

leetcode24


xxxxxxxxxx
26
1
class Solution {
2
public:
3
    ListNode* swapPairs(ListNode* head) 
4
    {
5
        if(head==nullptr||head->next==nullptr)
6
            return head;
7
        ListNode* dummyhead=new ListNode(-1,head);
8
        ListNode* pre=dummyhead;
9
        ListNode* first=head;
10
        ListNode* second=head->next;
11
        while(1)
12
        {
13
            first->next=second->next;
14
            second->next=first;
15
            pre->next=second;
16
            pre=first;
17
            first=pre->next;
18
            if(first==nullptr||first->next==nullptr)
19
                break;
20
            second=first->next;
21
        }
22
        first=dummyhead->next;
23
        delete dummyhead;
24
        return first;
25
    }
26
};

链表5:删除链表的倒数第N个节点

leetcode19

快慢指针法:先将右指针右移n个节点,再将左右指针一起右移,直到右指针的下一个位置为nullptr,此时左指针指向待删除节点的上一个位置


xxxxxxxxxx
21
1
class Solution {
2
public:
3
    ListNode* removeNthFromEnd(ListNode* head, int n) 
4
    {
5
        ListNode* dummyhead=new ListNode(-1,head);
6
        ListNode* left=dummyhead,*right=dummyhead;
7
        for(int i=0;i<n;++i)
8
            right=right->next;
9
        while(right->next!=nullptr)
10
        {
11
            right=right->next;
12
            left=left->next;
13
        }
14
        ListNode* rubbish=left->next;
15
        left->next=left->next->next;
16
        delete rubbish;
17
        ListNode* ret=dummyhead->next;
18
        delete dummyhead;
19
        return ret;
20
    }
21
};

链表6：相交链表

leetcode160


xxxxxxxxxx
50
1
class Solution {
2
public:
3
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
4
    {
5
        ListNode* p=headA;
6
        int alen=1,blen=1;
7
        while(p->next!=nullptr)
8
        {
9
            p=p->next;
10
            ++alen;
11
        }
12
        p=headB;
13
        while(p->next!=nullptr)
14
        {
15
            p=p->next;
16
            ++blen;
17
        }
18
        ListNode* p1;
19
        if(alen>blen)
20
        {
21
            p=headA;
22
            for(int i=0;i<alen-blen;++i)
23
            {
24
                p=p->next;
25
                if(p==headB)
26
                    return headB;
27
            }
28
            p1=headB;
29
        }
30
        else
31
        {
32
            p=headB;
33
            for(int i=0;i<blen-alen;++i)
34
            {
35
                p=p->next;
36
                if(p==headA)
37
                    return headA;
38
            }
39
            p1=headA;
40
        }
41
        while(p!=nullptr&&p1!=nullptr)
42
        {
43
            if(p==p1)
44
                return p;
45
            p=p->next;
46
            p1=p1->next;
47
        }
48
        return nullptr;
49
    }
50
};

链表7：环形链表II*

leetcode142


xxxxxxxxxx
5
1
[--------a-------][---------b--------]
2
_____________________________________ <--快慢指针在这里相遇
3
                 |___________________|
4
                 [----------c--------]
5

快慢指针法：

快指针一次移动2个节点，慢指针一次移动1个节点，移动完成后才检查二者是否相遇，两者相对速度1个节点，所以不会存在快指针越过慢指针而没有检测到的情况

对于慢指针 t=a+b

可以证明慢指针在圈里的路程不足一圈，不是t=a+b+k(b+c), 因为慢指针进入圈内时，快指针已经在圈内，慢指针要转完一圈，快指针就会转两圈，所以在慢指针转完一圈之前，快指针就会和慢指针相遇

对于快指针 2t=a+b+n(b+c)

所以a=(n-1)(b+c)+c

让两个指针分别从头节点和相遇点出发，二者一定会在环的入口处相遇

$O(n)$ $O(1)$

C++:


xxxxxxxxxx
26
1
class Solution {
2
public:
3
    ListNode *detectCycle(ListNode *head) 
4
    {
5
        ListNode* fast=head,*slow=head;
6
        while(1)
7
        {
8
            if(fast==nullptr||slow==nullptr)
9
                return nullptr;
10
            fast=fast->next;
11
            if(fast==nullptr)
12
                return nullptr;
13
            fast=fast->next;
14
            slow=slow->next;
15
            if(fast==slow)
16
                break;
17
        }
18
        ListNode* p=head;
19
        while(p!=fast)
20
        {
21
            p=p->next;
22
            fast=fast->next;
23
        }
24
        return p;
25
    }
26
};

python:


xxxxxxxxxx
19
1
class Solution:
2
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
        fast=head
4
        slow=head
5
        while 1:
6
            if fast==None or slow==None:
7
                return None
8
            fast=fast.next
9
            if fast==None:
10
                return None
11
            fast=fast.next
12
            slow=slow.next
13
            if fast==slow:
14
                break
15
        p=head
16
        while p!=fast:
17
            p=p.next
18
            fast=fast.next
19
        return p

哈希表1: 有效的字母异位词

leetcode242

简单题,大佬们可以直接跳过

用数组代替哈希表


xxxxxxxxxx
15
1
class Solution {
2
public:
3
    bool isAnagram(string s, string t) 
4
    {
5
        vector<int>vec(26);
6
        for(char& ch:s)
7
            ++vec[ch-'a'];
8
        for(char& ch:t)
9
            --vec[ch-'a'];
10
        for(int& n:vec)
11
            if(n!=0)
12
                return false;
13
        return true;
14
    }
15
};

哈希表2:两个数组的交集

leetcode349

简单题,大佬们可以直接跳过

python:


xxxxxxxxxx
11
1
class Solution:
2
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
3
        hash=dict()
4
        for n in nums1:
5
            hash[n]=1
6
        ret=[]
7
        for n in nums2:
8
            if n in hash and hash[n]==1:
9
                ret.append(n)
10
                hash[n]=0
11
        return ret

哈希表3:快乐数

leetcode202


xxxxxxxxxx
24
1
using ll=long long;
2
class Solution {
3
public:
4
    bool isHappy(int n) 
5
    {
6
        unordered_map<ll,int>hash;
7
        while(n!=1)
8
        {
9
            if(hash[n]==1)
10
                return false;
11
            else 
12
                hash[n]=1;
13
            ll num=0;
14
            while(n!=0)
15
            {
16
                ll tmp=n%10;
17
                num+=tmp*tmp;
18
                n/=10;
19
            }
20
            n=num;
21
        }
22
        return true;
23
    }
24
};

哈希表4:两数之和

leetcode1

经典好题

C++:


xxxxxxxxxx
17
1
class Solution {
2
public:
3
    vector<int> twoSum(vector<int>& nums, int target) 
4
    {
5
        unordered_map<int,int> hash;
6
        int i=1;
7
        for(auto num:nums)
8
        {
9
            if(hash[target-num]!=0)
10
                return {i-1,hash[target-num]-1};
11
            else
12
                hash[num]=i;
13
            ++i;
14
        }
15
        return {};
16
    }
17
};

python:


xxxxxxxxxx
9
1
class Solution:
2
    def twoSum(self, nums: List[int], target: int) -> List[int]:
3
        le=len(nums)
4
        dic=dict()
5
        for i in range(le):
6
            if nums[i] in dic:
7
                return [dic[nums[i]],i]
8
            else:
9
                dic[target-nums[i]]=i

哈希表5:四数相加II

leetcode454

$O(n^4)$ 会超时

$O(n^2)$


xxxxxxxxxx
16
1
class Solution {
2
public:
3
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) 
4
    {
5
        unordered_map<int,int>hash;
6
        int n=nums1.size();
7
        for(int i=0;i<n;++i)
8
            for(int j=0;j<n;++j)
9
                ++hash[-nums1[i]-nums2[j]];
10
        int ret=0;
11
        for(int i=0;i<n;++i)
12
            for(int j=0;j<n;++j)
13
                ret+=hash[nums3[i]+nums4[j]];
14
        return ret;
15
    }
16
};

哈希表6:赎金信

leetcode383

简单题,大佬们可以直接跳过

python:


xxxxxxxxxx
14
1
class Solution:
2
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
3
        hash={}
4
        for ch in magazine:
5
            if ch not in hash:
6
                hash[ch]=1
7
            else:
8
                hash[ch]+=1
9
        for ch in ransomNote:
10
            if ch not in hash or hash[ch]==0:
11
                return False
12
            else:
13
                hash[ch]-=1
14
        return True

哈希表6.9:两数之和 II - 输入有序数组

leetcode167

这一题是给下一题打基础用的

推荐看灵神的视频

C++:


xxxxxxxxxx
20
1
class Solution {
2
public:
3
    vector<int> twoSum(vector<int>& numbers, int target) 
4
    {
5
        int left=0,right=numbers.size()-1;
6
        int sum;
7
        while(1)
8
        {
9
            sum=numbers[left]+numbers[right];
10
            if(sum==target)
11
            {
12
                return vector<int>{left+1,right+1};
13
            }
14
            else if(sum>target)
15
                --right;
16
            else 
17
                ++left;
18
        }
19
    }
20
};

python:


xxxxxxxxxx
12
1
class Solution:
2
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
3
        left=0
4
        right=len(numbers)-1
5
        while 1:
6
            tmp=numbers[left]+numbers[right]
7
            if tmp==target:
8
                return [left+1,right+1]
9
            elif tmp>target:
10
                right-=1
11
            else:
12
                left+=1

课后作业

哈希表7:三数之和

leetcode15

这题不好做 😫

C++:


xxxxxxxxxx
34
1
class Solution {
2
public:
3
    vector<vector<int>> threeSum(vector<int>& nums) 
4
    {
5
        sort(nums.begin(),nums.end());
6
        vector<vector<int>>ret;
7
        for(int i=0;i<nums.size();++i)
8
        {
9
            while(i>0&&i<nums.size()&&nums[i]==nums[i-1])
10
                ++i;
11
            if(i==nums.size())
12
                break;
13
            int left=i+1,right=nums.size()-1;
14
            while(left<right)
15
            {
16
                int sum=-(nums[left]+nums[right]);
17
                if(sum==nums[i]&&left<right)
18
                {
19
                    vector<int>tmp={nums[i],nums[left],nums[right]};
20
                    ret.emplace_back(tmp);
21
                    while(right>0&&left<right&&nums[right-1]==nums[right])
22
                        --right;
23
                    if(right>0)
24
                        --right;
25
                }
26
                else if(sum<nums[i])
27
                    --right;
28
                else 
29
                    ++left;
30
            }
31
        }
32
        return ret;
33
    }
34
};

python:


xxxxxxxxxx
27
1
class Solution:
2
    def threeSum(self, nums: List[int]) -> List[List[int]]:
3
        nums.sort()
4
        ret=[]
5
        le=len(nums)
6
        idx=0
7
        while idx<le-2:
8
            while idx>0 and idx<le and nums[idx]==nums[idx-1]:
9
                idx+=1
10
            if(idx>=le-2):
11
                break
12
            target=-nums[idx]
13
            left=idx+1
14
            right=le-1
15
            while left<right:
16
                add=nums[left]+nums[right]
17
                if add==target:
18
                    ret.append([nums[idx],nums[left],nums[right]])
19
                    while right>left and nums[right]==nums[right-1]:
20
                        right-=1
21
                    right-=1
22
                elif add>target:
23
                    right-=1
24
                else:
25
                    left+=1
26
            idx+=1
27
        return ret

字符串1：反转字符串

leetcode344

双指针交换就行

C++:


xxxxxxxxxx
16
1
class Solution {
2
public:
3
    void reverseString(vector<char>& s) 
4
    {
5
        int left=0;
6
        int right=s.size()-1;
7
        while(left<right)
8
        {
9
            s[left]=s[left]^s[right];
10
            s[right]=s[left]^s[right];
11
            s[left]=s[left]^s[right];
12
            ++left;
13
            --right;
14
        }
15
    }
16
};

Javascript:


xxxxxxxxxx
17
1
/**
2
 * @param {character[]} s
3
 * @return {void} Do not return anything, modify s in-place instead.
4
 */
5
var reverseString = function(s) 
6
{
7
    let n=s.length;
8
    let left=0,right=n-1;
9
    while(left<right)
10
    {
11
        let tmp=s[left];
12
        s[left]=s[right];
13
        s[right]=tmp;
14
        ++left;
15
        --right;
16
    }
17
};

字符串2:反转字符串II

leetcode541


xxxxxxxxxx
17
1
class Solution {
2
public:
3
    string reverseStr(string s, int k) 
4
    {
5
        int n=0;
6
        int flag=1;
7
        for(;flag;++n)
8
        {
9
            auto beg=s.begin()+2*n*k;
10
            if(2*n*k+k>=s.size())
11
                flag=0;
12
            auto end=s.begin()+min((int)s.size(),2*n*k+k);
13
            reverse(beg,end);
14
        }
15
        return s;
16
    }
17
};

字符串3:替换空格

leetcode剑指offer05

算法很简单,可以拿这个检验一下自己对库函数的熟悉程度

Javascript:不用库函数


xxxxxxxxxx
16
1
/**
2
 * @param {string} s
3
 * @return {string}
4
 */
5
var replaceSpace = function(s) 
6
{
7
    let tmp="";
8
    for(var i=0;i<s.length;++i)
9
    {
10
        if(s[i]!=' ')
11
            tmp+=s[i];
12
        else
13
            tmp+="%20";
14
    }
15
    return tmp;
16
};

直接调用库函数:


xxxxxxxxxx
8
1
/**
2
 * @param {string} s
3
 * @return {string}
4
 */
5
var replaceSpace = function(s) 
6
{
7
    return s.replaceAll(' ',"%20");
8
};

python也有这个库函数:


xxxxxxxxxx
3
1
class Solution:
2
    def replaceSpace(self, s: str) -> str:
3
        return s.replace(" ","%20")

字符串4:反转字符串中的单词

leetcode151

JavaScript:


xxxxxxxxxx
30
1
/**
2
 * @param {string} s
3
 * @return {string}
4
 */
5
var reverseWords = function(s) 
6
{
7
    let arr=[];
8
    let tmp="",ret="";
9
    for(var i=0;i<s.length;++i)
10
    {
11
        if(s[i]!==" ")
12
        {
13
            tmp+=s[i];
14
        }
15
        else if(tmp!="")
16
        {
17
            arr.push(tmp);
18
            tmp="";
19
        }
20
    }
21
    if(tmp!="")
22
        arr.push(tmp);
23
    for(var i=arr.length-1;i>=0;--i)
24
    {
25
        ret+=arr[i];
26
        if(i!=0)
27
            ret+=" ";
28
    }
29
    return ret;
30
};

大佬的调用内置函数解法:


xxxxxxxxxx
3
1
var reverseWords = function(s) {
2
    return s.trim().split(/\s+/).reverse().join(' ');
3
};

trim()函数用于去除字符串两端的空格（空白字符），并返回处理后的字符串。
以下出自CSDN split( /\s+/)什么意思 split( /\s+/)的意思是将字符串以满足/\s+/这个正则表达式的字符来分割为一个数组。分割满足条件包括：制表符，换行符，回车符，垂直制表符，换页符在内的一个至无穷个类空格字符。其中： \s表示：匹配任何空白字符，包括空格、制表符、换页符等等。等价于[ \f\n\r\t\v]。 +表示：匹配前面的子表达式一次或多次。 split()：是js的一个用于把一个字符串分割成字符串数组的方法。
join()方法就是将array数据中每个元素都转为字符串，用自定义的连接符分割

字符串6:找出字符串中第一个匹配项的下标

leetcode28

KMP算法的经典例题

方法1：KMP算法

next数组样例1：

a	a	b	a	a	f
0	1	0	1	2	0

next数组样例2：

a	a	b	a	a	a	b
0	1	0	1	2	2	3

遍历next数组的指针指向下标为j处时，遇到不匹配，就回退到下标next[j-1]处

next数组的构造过程

i指向后缀表的末尾，j指向前缀表的末尾，每轮循环需要判断前后缀表的末尾元素能否加入前后缀表中，也就是比较needle[i]和needle[j]是否相等

前缀表和后缀表等长，末尾元素加入前后缀表后，长度都是j+1

初始化i=1，j=0


xxxxxxxxxx
40
1
class Solution {
2
public:
3
    int strStr(string haystack, string needle) //KMP
4
    {
5
        int n=haystack.size(),m=needle.size();
6
        //构造next数组
7
        vector<int>next(m);
8
        int i=1,j=0;
9
        while(i<m)
10
        {
11
            if(needle[i]==needle[j])
12
                next[i++]=++j;
13
            else if(j==0)
14
                next[i++]=0;
15
            else
16
                j=next[j-1];
17
        }
18
        //打印next数组检验
19
        // for(int& num:next)
20
        //     cout<<num<<' ';
21
        //匹配字符串
22
        i=0,j=0;
23
        while(i<n&&j<m)
24
        {
25
            if(haystack[i]==needle[j])
26
            {
27
                ++i;
28
                ++j;
29
            }
30
            else if(j==0)
31
                ++i;
32
            else
33
                j=next[j-1];
34
        }
35
        if(j==m)
36
            return i-m;
37
        else
38
            return -1;
39
    }
40
};

方法2：Rabin-Karp算法

这个算法实际上就是哈希表，ChatGPT的解释:

Rabin-Karp算法是一种字符串匹配算法，用于在一个文本串中查找一个模式串的出现位置。
算法的基本思想是通过哈希函数将模式串和文本串的子串进行比较。首先计算模式串的哈希值，然后依次计算文本串中所有长度为模式串长度的子串的哈希值，并与模式串的哈希值进行比较。如果哈希值相同，再逐个比较子串和模式串的每个字符是否相同，直到找到完全匹配的子串或者遍历完所有子串。
算法的优点是可以在平均情况下达到线性时间复杂度O(n+m)，其中n是文本串的长度，m是模式串的长度。然而，在最坏情况下，算法的时间复杂度为O((n-m+1)m)，即当哈希值的冲突比较多时，效率会下降。
总结来说，Rabin-Karp算法通过哈希函数加速字符串匹配，适用于处理长文本串和短模式串的情况。它在实际应用中常被用于字符串搜索、文本编辑器等领域。


xxxxxxxxxx
13
1
class Solution {
2
public:
3
    int strStr(string haystack, string needle) 
4
    {
5
        unordered_map<string,int>hash;
6
        hash[needle]=1;
7
        int m=needle.size(),n=haystack.size();
8
        for(int i=0;i<=n-m;++i)
9
            if(hash[haystack.substr(i,m)]==1)
10
                return i;
11
        return -1;
12
    }
13
};

字符串7：重复的子字符串

leetcode459

方法1：双指针


xxxxxxxxxx
25
1
class Solution:
2
    def repeatedSubstringPattern(self, s: str) -> bool:
3
        i=0  # 慢指针
4
        j=1  # 快指针
5
        n=len(s)
6
        tmp=0  # 记录flag改变时j的值，以便恢复
7
        flag=0  # flag=0表示未找到重复的部分 =1表示找到了
8
        while j<n:
9
            if flag==0:
10
                if s[i]==s[j] and n%j==0:
11
                    flag=1
12
                    tmp=j
13
                    i+=1
14
                    j+=1
15
                else:
16
                    j+=1
17
            else:
18
                if s[i]!=s[j]:
19
                    i=0
20
                    j=tmp+1
21
                    flag=0
22
                else:
23
                    i+=1
24
                    j+=1
25
        return flag==1

方法2：转化为字符串匹配问题


xxxxxxxxxx
7
1
class Solution {
2
public:
3
    bool repeatedSubstringPattern(string s) 
4
    {
5
        return (s+s).find(s,1)!=s.size();
6
    }
7
};

方法3：转化为字符串匹配问题，并利用KMP算法


xxxxxxxxxx
46
1
class Solution {
2
public:
3
    int strStr(string haystack, string needle) //KMP
4
    {
5
        int n=haystack.size(),m=needle.size();
6
        //构造next数组
7
        vector<int>next(m);
8
        int i=1,j=0;
9
        while(i<m)
10
        {
11
            if(needle[i]==needle[j])
12
                next[i++]=++j;
13
            else if(j==0)
14
                next[i++]=0;
15
            else
16
                j=next[j-1];
17
        }
18
        //打印next数组检验
19
        // for(int& num:next)
20
        //     cout<<num<<' ';
21
        //匹配字符串
22
        i=0,j=0;
23
        while(i<n&&j<m)
24
        {
25
            if(haystack[i]==needle[j])
26
            {
27
                ++i;
28
                ++j;
29
            }
30
            else if(j==0)
31
                ++i;
32
            else
33
                j=next[j-1];
34
        }
35
        if(j==m)
36
            return i-m;
37
        else
38
            return -1;
39
    }
40
    bool repeatedSubstringPattern(string s) 
41
    {
42
        string hay=s+s;
43
        hay.erase(0,1);
44
        return strStr(hay,s)!=s.size()-1;
45
    }
46
};

字符串8：有效数字

leetcode65

方法1：暴力if-else

笨人的这段代码比较乱，建议去看方法2，更易理解


xxxxxxxxxx
84
1
class Solution {
2
public:
3
    bool isNumber(string s) 
4
    {
5
        int idx=0;
6
        if(s[idx]=='+'||s[idx]=='-')
7
            ++idx;
8
        int flag1=0;//是否存在整数位
9
        int flag2=0;//判断小数点是否出现,对应小数点前没有数字的情况
10
        int flag3=0;//判断小数点是否出现,对应小数点前有数字的情况
11
        int flag4=0;//小数点后有没有整数位
12
        if(idx==s.size())
13
            return false;
14
        if(s[idx]=='.')
15
        {
16
            ++idx;
17
            flag2=1;
18
        }
19
        if(idx==s.size())
20
            return false;
21
        while(idx<s.size())
22
        {
23
            if(s[idx]>='0'&&s[idx]<='9')
24
            {
25
                ++idx;
26
                flag1=1;
27
            }
28
            else
29
                break;
30
        }
31
        if(idx==s.size())
32
        {
33
            return flag1;
34
        }
35
        if(flag2==1&&flag1==0)
36
            return false;
37
        if(flag2==1&&idx<s.size()&&s[idx]=='.')
38
            return false;
39
        if(flag2==0&&idx<s.size()&&s[idx]=='.')
40
        {
41
            ++idx;
42
            flag3=1;
43
        }
44
        while(idx<s.size())
45
        {
46
            if(s[idx]>='0'&&s[idx]<='9')
47
            {
48
                ++idx;
49
                flag4=1;
50
            }
51
            else
52
                break;
53
        }
54
        if(flag1==0&&flag4==0)
55
            return false;
56
        
57
        if(idx<s.size()&&(s[idx]=='e'||s[idx]=='E'))
58
        {
59
            ++idx;
60
            if(idx==s.size())
61
                return false;
62
            if(s[idx]=='+'||s[idx]=='-')
63
                ++idx;
64
            if(idx==s.size())
65
                return false;
66
            int flag5=0;
67
            while(idx<s.size())
68
            {
69
                if(s[idx]>='0'&&s[idx]<='9')
70
                {
71
                    ++idx;
72
                    flag5=1;
73
                }
74
                else
75
                    break;
76
            }
77
            if(flag5==1&&idx==s.size())
78
                return true;
79
        }
80
        if(idx==s.size())
81
            return true;
82
        return false;
83
    }
84
};

0ms 5.8MB

方法2：有限状态自动机

参考文献

初始状态
符号位
整数部分
左侧有整数的小数点
左侧无整数的小数点（根据前面的第二条额外规则，需要对左侧有无整数的两种小数点做区分）
小数部分
字符 e
指数部分的符号位
指数部分的整数部分

(图片出自力扣官方题解)

最后只有cur==2||cur==3||cur==5||cur==8时返回true


xxxxxxxxxx
86
1
class Solution {
2
public:
3
    bool isNumber(string s) 
4
    {
5
        int cur=0;//当前状态
6
        int idx=0;//当前下标
7
        for(;idx<s.size();++idx)
8
        {
9
            switch(cur)
10
            {
11
                case 0:
12
                    if(s[idx]=='+'||s[idx]=='-')
13
                        cur=1;
14
                    else if(s[idx]=='.')
15
                        cur=4;
16
                    else if(s[idx]>='0'&&s[idx]<='9')
17
                        cur=2;
18
                    else
19
                        return false;
20
                break;
21
                case 1:
22
                    if(s[idx]>='0'&&s[idx]<='9')
23
                        cur=2;
24
                    else if(s[idx]=='.')
25
                        cur=4;
26
                    else
27
                        return false;
28
                break;
29
                case 2:
30
                    if(s[idx]>='0'&&s[idx]<='9')
31
                        cur=2;
32
                    else if(s[idx]=='.')
33
                        cur=3;
34
                    else if(s[idx]=='e'||s[idx]=='E')
35
                        cur=6;
36
                    else
37
                        return false;
38
                break;    
39
                case 3:
40
                    if(s[idx]=='e'||s[idx]=='E')
41
                        cur=6;
42
                    else if(s[idx]>='0'&&s[idx]<='9')
43
                        cur=5;
44
                    else 
45
                        return false;
46
                break;
47
                case 4:
48
                    if(s[idx]>='0'&&s[idx]<='9')
49
                        cur=5;
50
                    else
51
                        return false;
52
                break;
53
                case 5:
54
                    if(s[idx]>='0'&&s[idx]<='9')
55
                        cur=5;
56
                    else if(s[idx]=='e')
57
                        cur=6;
58
                    else
59
                        return false;
60
                break;
61
                case 6:
62
                    if(s[idx]=='+'||s[idx]=='-')
63
                        cur=7;
64
                    else if(s[idx]>='0'&&s[idx]<='9')
65
                        cur=8;
66
                    else 
67
                        return false;
68
                break;
69
                case 7:
70
                    if(s[idx]>='0'&&s[idx]<='9')
71
                        cur=8;
72
                    else
73
                        return false;
74
                break;
75
                case 8:
76
                    if(s[idx]>='0'&&s[idx]<='9')
77
                        cur=8;
78
                    else
79
                        return false;
80
                break;
81
            }
82
        }
83
        //此时idx==s.size()
84
        return cur==2||cur==3||cur==5||cur==8;
85
    }
86
};

0ms 5.9MB

方法3：正则表达式

C++的正则表达式库

正则表达式大全

代码粘贴自评论区大佬

正在表达式的构造耗时很长，所以建议采用第二段代码，避免重复构造


xxxxxxxxxx
6
1
class Solution {
2
public:
3
    bool isNumber(string str) {
4
        return regex_match(str, regex("[+-]?(\\d+\\.?\\d*|\\.\\d+)([Ee][+-]?\\d+)?"));
5
    }
6
};

1884ms,259.3MB


xxxxxxxxxx
10
1
class Solution {
2
public:
3
    static const regex pattern;
4

5
    bool isNumber(string str) {
6
        return regex_match(str, pattern);
7
    }
8
};
9

10
const regex Solution::pattern("[+-]?(\\d+\\.?\\d*|\\.\\d+)([Ee][+-]?\\d+)?");

12ms 9MB

字符串9：验证IP地址

正则表达式


xxxxxxxxxx
16
1
class Solution {
2
public:
3
    static const regex pattern4;
4
    static const regex pattern6;
5
    string validIPAddress(string queryIP) 
6
    {
7
        if(regex_match(queryIP,pattern4))
8
            return "IPv4";
9
        else if(regex_match(queryIP,pattern6))
10
            return "IPv6";
11
        else
12
            return "Neither";        
13
    }
14
};
15
const regex Solution::pattern4("((25[0-5]|2[0-4][0-9]|1\\d\\d|[1-9]?\\d)\\.){3}(25[0-5]|2[0-4][0-9]|1\\d\\d|[1-9]?\\d)");
16
const regex Solution::pattern6("([0-9a-fA-F]{1,4}\\:){7}([0-9a-fA-F]{1,4})");

字符串10：实现Trie(前缀树)

leetcode208

字典树的经典例题


xxxxxxxxxx
63
1
class TrieNode{
2
public:
3
    char ch;
4
    vector<TrieNode*>next;
5
    TrieNode(char ch_=0):ch(ch_),next(27,nullptr){}
6
};
7
class Trie {
8
public:
9
    TrieNode* root;
10
    Trie() {
11
        root=new TrieNode;
12
    }
13
    
14
    void insert(string word) {
15
        TrieNode* cur=root;
16
        for(char& w:word)
17
        {
18
            int idx=w-'a';
19
            if(cur->next[idx]!=nullptr)
20
                cur=cur->next[idx];
21
            else
22
            {
23
                cur->next[idx]=new TrieNode(w);
24
                cur=cur->next[idx];
25
            }
26
        }
27
        cur->next[26]=new TrieNode;//标识单词的结尾
28
    }
29
    
30
    bool search(string word) {
31
        TrieNode* cur=root;
32
        for(char& w:word)
33
        {
34
            int idx=w-'a';
35
            if(cur->next[idx]==nullptr)
36
                return false;
37
            else
38
                cur=cur->next[idx];
39
        }
40
        return cur->next[26]!=nullptr;
41
    }
42
    
43
    bool startsWith(string prefix) {
44
        TrieNode* cur=root;
45
        for(char& w:prefix)
46
        {
47
            int idx=w-'a';
48
            if(cur->next[idx]==nullptr)
49
                return false;
50
            else
51
                cur=cur->next[idx];
52
        }
53
        return true;
54
    }
55
};
56

57
/**
58
 * Your Trie object will be instantiated and called as such:
59
 * Trie* obj = new Trie();
60
 * obj->insert(word);
61
 * bool param_2 = obj->search(word);
62
 * bool param_3 = obj->startsWith(prefix);
63
 */

字符串11：连接词

leetcode472

前缀树+记忆化搜索


xxxxxxxxxx
71
1
class TrieNode{//字典树节点
2
public:
3
    vector<TrieNode*>next;
4
    TrieNode():next(27,nullptr){}
5
};
6
class Solution {
7
public:
8
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
9
        TrieNode* root=new TrieNode;
10
        for(string& str:words)//将所有的单词插入前缀树（字典树）
11
        {
12
            if(str.size()==0)
13
                continue;
14
            TrieNode* cur=root;
15
            for(char& ch:str)
16
            {
17
                int idx=ch-'a';
18
                if(cur->next[idx]==nullptr)
19
                {
20
                    cur->next[idx]=new TrieNode;
21
                    cur=cur->next[idx];
22
                }
23
                else
24
                    cur=cur->next[idx];
25
            }
26
            cur->next[26]=new TrieNode;//标识单词的结尾
27
        }
28
        vector<string>ret;
29
        for(string& str:words)//查找符合题意的字符串
30
        {
31
            if(str.size()==0)
32
                continue;
33
            queue<pair<int,int>>que;//利用队列
34
            que.push(make_pair(-1,-2));
35
            vector<int>isvisited(str.size());
36
            while(!que.empty())
37
            {
38
                
39
                int pos=que.front().first+1;
40
                int pre=que.front().second;
41
                que.pop();
42
                if(pos!=str.size())//记忆化搜索，否则会超时
43
                {
44
                    if(isvisited[pos]==0)
45
                        isvisited[pos]=1;
46
                    else
47
                        continue;
48
                }
49
                TrieNode*cur=root;
50
                int i;
51
                for(i=pos;i<str.size();++i)
52
                {
53
                    int idx=str[i]-'a';
54
                    if(cur->next[idx]!=nullptr)
55
                        cur=cur->next[idx];
56
                    else 
57
                        break;  
58
                    if(cur->next[26]!=nullptr)
59
                        que.push(make_pair(i,pos));
60
                    
61
                }
62
                if(pos==str.size()&&pre>0)
63
                {
64
                    ret.emplace_back(str);
65
                    break;
66
                }
67
            }
68
        }
69
        return ret;
70
    }
71
};

前缀树+DFS+记忆化搜索


xxxxxxxxxx
75
1
class TrieNode{
2
public:
3
    bool isend;//是不是单词的结尾
4
    vector<TrieNode*>next;
5
    TrieNode(bool isend_=false):isend(isend_),next(26,nullptr){}
6
};
7
class Solution {
8
public:
9
    TrieNode* root;
10
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
11
        root=new TrieNode;
12
        sort(words.begin(),words.end(),[&](string& a,string& b){
13
            return a.size()<b.size();
14
        });
15
        vector<string>ret;
16
        for(string& str:words)
17
        {
18
            // if(str.size()==0)
19
            //     continue;
20
            vector<bool>isvisited(str.size(),false);
21
            bool flag=false;
22
            function<void(int)>dfs=[&](int i)
23
            {
24
                if(flag)
25
                    return;
26
                isvisited[i]=true;
27
                TrieNode* p=root;
28
                for(int j=i;j<str.size();++j)
29
                {
30
                    
31
                    int idx=str[j]-'a';
32
                    if(p->next[idx]!=nullptr)
33
                    {
34
                        p=p->next[idx];
35
                    }
36
                    else
37
                    {
38
                        return;
39
                    }
40
                    if(j==str.size()-1)
41
                    {
42
                        if(i!=0&&p->isend)
43
                        {
44
                            ret.emplace_back(str);
45
                            flag=true;
46
                        }
47
                        return;
48
                    }
49
                    if(p->isend)
50
                    {
51
                        if(!isvisited[j+1])
52
                            dfs(j+1);
53
                    }
54
                    if(flag)
55
                        return;
56
                }
57
            };
58
            dfs(0);
59
            TrieNode* p=root;
60
            for(char& ch:str)
61
            {
62
                int idx=ch-'a';
63
                if(p->next[idx]!=nullptr)
64
                    p=p->next[idx];
65
                else
66
                {
67
                    p->next[idx]=new TrieNode;
68
                    p=p->next[idx];
69
                }
70
            }
71
            p->isend=true;
72
        }
73
        return ret;
74
    }
75
};

字符串12：字符流

leetcode1032

AC自动机的经典例题

OI-wiki:AC自动机


xxxxxxxxxx
79
1
class TrieNode{
2
public:
3
    TrieNode* fail;
4
    vector<TrieNode*>next;
5
    bool isend;
6
    TrieNode():fail(nullptr),next(26,nullptr),isend(false){}
7
};
8
class StreamChecker {
9
public:
10
    TrieNode* root;
11
    TrieNode* pos;
12
    StreamChecker(vector<string>& words) 
13
    {
14
        root=new TrieNode;
15
        root->fail=root;
16
        pos=root;
17
        for(string& word:words)//第一次遍历：构造字典树
18
        {
19
            TrieNode* p=root;
20
            for(char& ch:word)
21
            {
22
                int idx=ch-'a';
23
                if(p->next[idx]==nullptr)
24
                    p->next[idx]=new TrieNode;
25
                p=p->next[idx];
26
            }
27
            p->isend=true;
28
        }
29
        //设置fail指针 注意：这里必须广度优先遍历，不允许深度优先遍历
30
        queue<TrieNode*>q;
31
        q.push(root);
32
        while(!q.empty())
33
        {
34
            TrieNode* front=q.front();
35
            q.pop();
36
            for(int i=0;i<26;++i)
37
            {
38
                if(front->next[i]==nullptr)
39
                    continue;
40
                else
41
                    q.push(front->next[i]);
42
                TrieNode* f=front->fail;
43
                while(f!=root&&f->next[i]==nullptr)
44
                    f=f->fail;
45
                if(front!=root&&f->next[i]!=nullptr)
46
                    front->next[i]->fail=f->next[i];
47
                else
48
                    front->next[i]->fail=root;
49
            }
50
        }  
51
    }
52
    bool query(char letter) 
53
    {
54
        int idx=letter-'a';
55
        while(pos!=root&&pos->next[idx]==nullptr)
56
        {
57
            pos=pos->fail;
58
        }
59
        TrieNode* tmp=pos;
60
        if(pos->next[idx]!=nullptr)
61
            pos=pos->next[idx];
62
        while(tmp!=root)
63
        {
64
            if(tmp->next[idx]!=nullptr&&tmp->next[idx]->isend)
65
                return true;
66
            else
67
                tmp=tmp->fail;
68
        }
69
        if(tmp->next[idx]!=nullptr&&tmp->next[idx]->isend)
70
            return true;
71
        return false;
72
    }
73
};
74

75
/**
76
 * Your StreamChecker object will be instantiated and called as such:
77
 * StreamChecker* obj = new StreamChecker(words);
78
 * bool param_1 = obj->query(letter);
79
 */

栈和队列4:有效的括号

leetcode20

相当基础的栈的应用


xxxxxxxxxx
31
1
class Solution {
2
public:
3
    stack<char>st;
4
    bool isValid(string s) 
5
    {
6
        char ch;
7
        for(int i=0;s[i]!=0;i++)
8
        {
9
            if(s[i]=='('||s[i]=='['||s[i]=='{')
10
                st.push(s[i]);
11
            else
12
            {
13
                if(st.empty())
14
                    return false;
15
                else 
16
                {
17
                    ch=st.top();
18
                    st.pop();
19
                    if(abs(ch-s[i])<3&&ch!=s[i])
20
                        continue;
21
                    else
22
                        return false;
23
                }
24
            }
25
        }
26
        if(st.empty())
27
        return true;
28
        else
29
        return false;
30
    }
31
};

栈和队列5:删除字符串中的所有相邻重复项

leetcode1047


xxxxxxxxxx
28
1
class Solution {
2
public:
3
    string removeDuplicates(string s) 
4
    {
5
        stack<char>sta;
6
        int len=0;
7
        for(char& ch:s)
8
        {
9
            if(sta.empty()||sta.top()!=ch)
10
            {
11
                sta.push(ch);
12
                ++len;
13
            }
14
            else
15
            {
16
                sta.pop();
17
                --len;
18
            }
19
        }
20
        string ret(len,0);
21
        for(int i=len-1;i>=0;--i)
22
        {
23
            ret[i]=sta.top();
24
            sta.pop();
25
        }
26
        return ret;
27
    }
28
};

栈和队列6:逆波兰表达式求值

leetcode150

以下为王道考研数据结构的笔记:栈在表达式求值中的应用

序号表示各个运算符的执行顺序


xxxxxxxxxx
4
1
((15 ÷ (7-(1 + 1)))×3) - (2+(1 + 1))   中缀表达式
2
     ③   ②   ①     ④   ⑦    ⑥   ⑤                    
3
         ① ② ③   ④       ⑤ ⑥ ⑦                                   
4
15 7 1 1 + - ÷ 3 × 2 1 1 + + -         后缀表达式

C++:


xxxxxxxxxx
38
1
class Solution {
2
public:
3
    int evalRPN(vector<string>& tokens) 
4
    {
5
        stack<int>sta;
6
        for(string& s:tokens)
7
        {
8
            if(s=="+"||s=="-"||s=="*"||s=="/")
9
            {
10
                int a=sta.top();
11
                sta.pop();
12
                int b=sta.top();
13
                sta.pop();
14
                switch(s[0])
15
                {
16
                    case '*':
17
                        sta.push(b*a);
18
                    break;
19
                    case '/':
20
                        sta.push(b/a);
21
                    break;
22
                    case '+':
23
                        sta.push(b+a);
24
                    break;
25
                    case '-':
26
                        sta.push(b-a);
27
                    break;
28
                }
29
            }
30
            else
31
            {
32
                int num=stoi(s);
33
                sta.push(num);
34
            }
35
        }
36
        return sta.top();
37
    }
38
};

栈和队列7：基本计算器

leetcode224


xxxxxxxxxx
85
1
class Solution {
2
public:
3
    int calculate(string s) 
4
    {
5
        stack<char>oper;
6
        stack<int>nums;
7
        int tmp=0;
8
        for(int i=0;i<s.size();++i)
9
        {
10
            char ch=s[i];
11
            if(ch>='0'&&ch<='9')
12
            {
13
                tmp*=10;
14
                tmp+=ch-'0';
15
                if(i+1==s.size()||s[i+1]<'0'||s[i+1]>'9')
16
                {
17
                    nums.push(tmp);
18
                    tmp=0;
19
                }
20
            }
21
            else
22
            {
23
                if(ch=='(')
24
                    oper.push('(');
25
                else if(ch=='+'||ch=='-')
26
                {
27
                    if(ch=='-')
28
                    {
29
                        int j=i-1;
30
                        while(j>=0&&s[j]==' ')
31
                            --j;
32
                        if(j==-1||s[j]=='(')
33
                            nums.push(0);
34
                    }
35
                    while(!oper.empty()&&(oper.top()=='+'||oper.top()=='-'))
36
                    {
37
                        int right=nums.top();
38
                        nums.pop();
39
                        int left=nums.top();
40
                        nums.pop();
41
                        if(oper.top()=='+')
42
                            nums.push(left+right);
43
                        else
44
                            nums.push(left-right);
45
                        oper.pop();
46
                    }
47
                    oper.push(ch);
48
                }
49
                else if(ch==')')
50
                {
51
                    while(!oper.empty())
52
                    {
53
                        if(oper.top()=='(')
54
                        {
55
                            oper.pop();
56
                            break;
57
                        }
58
                        int right=nums.top();
59
                        nums.pop();
60
                        int left=nums.top();
61
                        nums.pop();
62
                        if(oper.top()=='+')
63
                            nums.push(left+right);
64
                        else
65
                            nums.push(left-right);
66
                        oper.pop();
67
                    }
68
                }
69
            }
70
        }
71
        while(!oper.empty())
72
        {
73
            int right=nums.top();
74
            nums.pop();
75
            int left=nums.top();
76
            nums.pop();
77
            if(oper.top()=='+')
78
                nums.push(left+right);
79
            else
80
                nums.push(left-right);
81
            oper.pop();
82
        }
83
        return nums.top();
84
    }
85
};

栈和队列8：基本计算器II

leetcode227

代码在上一题的基础上改了一下，可以支持对正负数的+-*/和括号运算


xxxxxxxxxx
109
1
class Solution {
2
public:
3
    int calculate(string s) 
4
    {
5
        stack<char>oper;
6
        stack<int>nums;
7
        int tmp=0;
8
        for(int i=0;i<s.size();++i)
9
        {
10
            char ch=s[i];
11
            if(ch>='0'&&ch<='9')
12
            {
13
                tmp*=10;
14
                tmp+=ch-'0';
15
                if(i+1==s.size()||s[i+1]<'0'||s[i+1]>'9')
16
                {
17
                    nums.push(tmp);
18
                    tmp=0;
19
                }
20
            }
21
            else
22
            {
23
                if(ch=='(')
24
                    oper.push('(');
25
                else if(ch=='+'||ch=='-')
26
                {
27
                    if(ch=='-')
28
                    {
29
                        int j=i-1;
30
                        while(j>=0&&s[j]==' ')
31
                            --j;
32
                        if(j==-1||s[j]=='(')
33
                            nums.push(0);
34
                    }
35
                    while(!oper.empty()&&(oper.top()=='+'||oper.top()=='-'||oper.top()=='*'||oper.top()=='/'))
36
                    {
37
                        int right=nums.top();
38
                        nums.pop();
39
                        int left=nums.top();
40
                        nums.pop();
41
                        if(oper.top()=='+')
42
                            nums.push(left+right);
43
                        else if(oper.top()=='-')
44
                            nums.push(left-right);
45
                        else if(oper.top()=='*')
46
                            nums.push(left*right);
47
                        else
48
                            nums.push(left/right);
49
                        oper.pop();
50
                    }
51
                    oper.push(ch);
52
                }
53
                else if(ch=='*'||ch=='/')
54
                {
55
                    while(!oper.empty()&&(oper.top()=='*'||oper.top()=='/'))
56
                    {
57
                        int right=nums.top();
58
                        nums.pop();
59
                        int left=nums.top();
60
                        nums.pop();
61
                        if(oper.top()=='*')
62
                            nums.push(left*right);
63
                        else
64
                            nums.push(left/right);
65
                        oper.pop();
66
                    }
67
                    oper.push(ch);
68
                }
69
                else if(ch==')')
70
                {
71
                    while(!oper.empty())
72
                    {
73
                        if(oper.top()=='(')
74
                        {
75
                            oper.pop();
76
                            break;
77
                        }
78
                        int right=nums.top();
79
                        nums.pop();
80
                        int left=nums.top();
81
                        nums.pop();
82
                        if(oper.top()=='+')
83
                            nums.push(left+right);
84
                        else
85
                            nums.push(left-right);
86
                        oper.pop();
87
                    }
88
                }
89
            }
90
        }
91
        while(!oper.empty())
92
        {
93
            int right=nums.top();
94
            nums.pop();
95
            int left=nums.top();
96
            nums.pop();
97
            if(oper.top()=='+')
98
                nums.push(left+right);
99
            else if(oper.top()=='-')
100
                nums.push(left-right);
101
            else if(oper.top()=='*')
102
                nums.push(left*right);
103
            else
104
                nums.push(left/right);
105
            oper.pop();
106
        }
107
        return nums.top();
108
    }
109
};

二叉树2.递归遍历

先序遍历模板

C++:


xxxxxxxxxx
28
1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10
 * };
11
 */
12
class Solution {
13
public:
14
    vector<int> preorderTraversal(TreeNode* root) 
15
    {
16
        vector<int>ret;
17
        function<void(TreeNode*)>dfs=[&](TreeNode* head)
18
        {
19
            if(head==nullptr)
20
                return;
21
            ret.emplace_back(head->val);
22
            dfs(head->left);
23
            dfs(head->right);
24
        };
25
        dfs(root);
26
        return ret;
27
    }
28
};

python:


xxxxxxxxxx
17
1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
9
        arr=[]
10
        def dfs(TreeNode):
11
            if TreeNode==None:
12
                return
13
            arr.append(TreeNode.val)
14
            dfs(TreeNode.left)
15
            dfs(TreeNode.right)
16
        dfs(root)
17
        return arr

中序遍历模板：

和上面代码基本一样，交换它们的顺序：


xxxxxxxxxx
3
1
dfs(head->left);
2
ret.emplace_back(head->val);
3
dfs(head->right);

后序遍历:


xxxxxxxxxx
3
1
dfs(head->left);
2
dfs(head->right);
3
ret.emplace_back(head->val);

二叉树3.非递归遍历

用栈模拟递归的过程

写出二叉树的非递归遍历很难么？这次让你不再害怕非递归！|二叉树的非递归遍历 | 二叉树的遍历迭代法 | 前序与中(参考视频)

先序遍历:

注意:因为栈是先进后出的,先将右子节点入栈,再让左子节点入栈

C++:


xxxxxxxxxx
20
1
class Solution {
2
public:
3
    vector<int> preorderTraversal(TreeNode* root) 
4
    {
5
        stack<TreeNode*>sta;
6
        sta.push(root);
7
        vector<int>ret;
8
        while(!sta.empty())
9
        {
10
            TreeNode* cur=sta.top();
11
            sta.pop();
12
            if(cur==nullptr)
13
                continue;
14
            ret.emplace_back(cur->val);
15
            sta.push(cur->right);
16
            sta.push(cur->left);
17
        }
18
        return ret;
19
    }
20
};

Python:


xxxxxxxxxx
12
1
class Solution:
2
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
3
        arr=[]
4
        stack=[root]
5
        while len(stack)!=0:
6
            cur=stack.pop()
7
            if cur==None:
8
                continue
9
            arr.append(cur.val)
10
            stack.append(cur.right)
11
            stack.append(cur.left)
12
        return arr

后序遍历:

前序遍历是按照中左右遍历的

如果把前序遍历代码中


xxxxxxxxxx
2
1
sta.push(cur->right);
2
sta.push(cur->left);

颠倒顺序, 变成


xxxxxxxxxx
2
1
sta.push(cur->left);
2
sta.push(cur->right);

遍历顺序变成中右左

最后的arr数组进行反转,遍历序列就会变成左右中后序遍历序列

C++:


xxxxxxxxxx
21
1
class Solution {
2
public:
3
    vector<int> postorderTraversal(TreeNode* root) 
4
    {
5
        stack<TreeNode*>sta;
6
        sta.push(root);
7
        vector<int>ret;
8
        while(!sta.empty())
9
        {
10
            TreeNode* cur=sta.top();
11
            sta.pop();
12
            if(cur==nullptr)
13
                continue;
14
            ret.emplace_back(cur->val);
15
            sta.push(cur->left);
16
            sta.push(cur->right);            
17
        }
18
        reverse(ret.begin(),ret.end());
19
        return ret;
20
    }
21
};

Python:


xxxxxxxxxx
13
1
class Solution:
2
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
3
        arr=[]
4
        stack=[root]
5
        while len(stack)!=0:
6
            cur=stack.pop()
7
            if cur==None:
8
                continue
9
            arr.append(cur.val)
10
            stack.append(cur.left)
11
            stack.append(cur.right)
12
        arr=arr[::-1]
13
        return arr

中序遍历:*


xxxxxxxxxx
48
1
class Solution {
2
public:
3
    vector<int> inorderTraversal(TreeNode* root) 
4
    {
5
        int flag=1;//1为左模式，2为右模式
6
        stack<TreeNode*>sta;
7
        vector<int>ret;
8
        if(root==nullptr)
9
            return ret;
10
        TreeNode* p=root;
11
        sta.push(p);//孩子节点的入栈由父节点负责，头节点是例外
12
        while(1)
13
        {
14
            if(flag==1)//左模式
15
            {
16
                if(p->left!=nullptr)
17
                {
18
                    sta.push(p->left);
19
                    p=p->left;
20
                }
21
                else
22
                {
23
                    flag=2;
24
                    ret.emplace_back(p->val);
25
                    sta.pop();
26
                }
27
            }
28
            else//右模式
29
            {
30
                if(p->right!=nullptr)
31
                {
32
                    flag=1;
33
                    sta.push(p->right);
34
                    p=p->right;
35
                }
36
                else
37
                {
38
                    if(sta.empty())
39
                        break;
40
                    p=sta.top();
41
                    sta.pop();
42
                    ret.emplace_back(p->val);
43
                }
44
            }
45
        }
46
        return ret;
47
    }
48
};

二叉树5：层序遍历

leetcode102


xxxxxxxxxx
25
1
typedef struct TreeNode treenode;
2
class Solution {
3
public:
4
    vector<vector<int>> ret;
5
    queue<pair<treenode*,int>> que;
6
    vector<vector<int>> levelOrder(TreeNode* root) 
7
    {
8
        que.push(make_pair(root,0));
9
        if(root==NULL)
10
            return ret;
11
        while(!que.empty())
12
        {
13
            treenode* cur=que.front().first;
14
            int floor=que.front().second;
15
            ret.resize(floor+1);
16
            que.pop();
17
            if(cur->left!=NULL)
18
            que.push(make_pair(cur->left,floor+1));
19
            if(cur->right!=NULL)
20
            que.push(make_pair(cur->right,floor+1));
21
            ret[floor].emplace_back(cur->val);
22
        }
23
        return ret;
24
    }
25
};

二叉树6：翻转二叉树

leetcode226


xxxxxxxxxx
17
1
class Solution {
2
public:
3
    TreeNode* invertTree(TreeNode* root) 
4
    {
5
        function<void(TreeNode*)>dfs=[&](TreeNode* cur)
6
        {
7
            swap(cur->left,cur->right);
8
            if(cur->left!=nullptr)
9
                dfs(cur->left);
10
            if(cur->right!=nullptr)
11
                dfs(cur->right);
12
        };
13
        if(root!=nullptr)
14
            dfs(root);
15
        return root;
16
    }
17
};

二叉树8：对称二叉树

leetcode101


xxxxxxxxxx
28
1
class Solution {
2
public:
3
    bool isSymmetric(TreeNode* root) 
4
    {
5
        bool ret=true;
6
        function<void(TreeNode*,TreeNode*)>dfs=[&](TreeNode*p1,TreeNode*p2)
7
        {
8
            if(!ret)
9
                return;
10
            if(p1!=nullptr&&p2!=nullptr)
11
            {
12
                if(p1->val!=p2->val)
13
                {
14
                    ret=false;
15
                    return;
16
                }
17
                dfs(p1->right,p2->left);
18
                dfs(p1->left,p2->right);
19
            }
20
            else if(p1==nullptr&&p2==nullptr)
21
                return;
22
            else
23
                ret=false;
24
        };
25
        dfs(root->left,root->right);
26
        return ret;
27
    }
28
};

二叉树9:二叉树的最大深度

leetcode104


xxxxxxxxxx
18
1
class Solution {
2
public:
3
    int maxDepth(TreeNode* root) 
4
    {
5
        int ret=0;
6
        function<void(TreeNode*,int)>dfs=[&](TreeNode* cur,int idx)
7
        {
8
            ret=max(ret,idx);
9
            if(cur->left!=nullptr)
10
                dfs(cur->left,idx+1);
11
            if(cur->right!=nullptr)
12
                dfs(cur->right,idx+1);
13
        };
14
        if(root!=nullptr)
15
            dfs(root,1);
16
        return ret;
17
    }
18
};

二叉树10:二叉树的最小深度

leetcode111


xxxxxxxxxx
23
1
class Solution {
2
public:
3
    int minDepth(TreeNode* root) 
4
    {
5
        int ret=0x7fffffff;
6
        function<void(TreeNode*,int)>dfs=[&](TreeNode* cur,int idx)
7
        {
8
            if(cur->left!=nullptr)
9
                dfs(cur->left,idx+1);
10
            if(cur->right!=nullptr)
11
                dfs(cur->right,idx+1);
12
            if(cur->left==nullptr&&cur->right==nullptr)
13
            {
14
                ret=min(ret,idx);
15
            }
16
        };
17
        if(root!=nullptr)
18
            dfs(root,1);
19
        else
20
            ret=0;
21
        return ret;
22
    }
23
};

二叉树11:完全二叉树的节点个数

leetcode222

方法1:二分查找+位运算

(思路同力扣官方题解)


xxxxxxxxxx
44
1
class Solution {
2
public:
3
    int countNodes(TreeNode* root) 
4
    {
5
        if(root==nullptr)
6
            return 0;
7
        int ret=0;
8
        int h=2;//计算二叉树的层数
9
        TreeNode* p=root;
10
        while(p->right!=nullptr)
11
        {
12
            p=p->right;
13
            ++h;
14
        }
15
        int left=1,right;
16
        for(int i=1;i<h;++i)
17
            left*=2;
18
        right=left*2-1;
19
        while(left<=right)
20
        {
21
            int aver=(left+right)/2;
22
            vector<int>bits(h);
23
            int tmp=aver;
24
            for(int i=h-1;i>=0;--i)
25
            {
26
                bits[i]=tmp%2;
27
                tmp/=2;
28
            }
29
            p=root;
30
            for(int i=1;i<h;++i)
31
            {
32
                if(bits[i]==1)
33
                    p=p->right;
34
                else
35
                    p=p->left;
36
            }
37
            if(p==nullptr)
38
                right=aver-1;
39
            else
40
                left=aver+1;
41
        }
42
        return right;
43
    }
44
};

$O(\log^2n)$

$h=\lceil\log_2(n+1)\rceil$

$O(h)$ 的时间确定二叉树的深度

$h$ $O(h)$ $2^{h-1}$ $2^{h}-1$ $2^{h-1}$ $O(\log(2^{h-1}))=O(h-1)$ .

$O(h^2)=O(\log^2n)$

$h$ $O(\log n)$

方法2:寻找满二叉树

参考视频

这个方法利用递归, 更容易写😋

$h$ $2^h-1$

$2^n$ 可以写作1 << n


xxxxxxxxxx
24
1
class Solution {
2
public:
3
    int countNodes(TreeNode* root) 
4
    {
5
        if(root==nullptr)
6
            return 0;
7
        int ldepth=1,rdepth=1;
8
        TreeNode* p=root;
9
        while(p->left!=nullptr)
10
        {
11
            p=p->left;
12
            ++ldepth;
13
        }
14
        p=root;
15
        while(p->right!=nullptr)
16
        {
17
            p=p->right;
18
            ++rdepth;
19
        }
20
        if(ldepth==rdepth)
21
            return (1 << ldepth) - 1;
22
        else return countNodes(root->left)+countNodes(root->right)+1;
23
    }
24
};

$O(\log^2n)$

$h$ $O(h)$ $O(h^2)=O(\log^2n)$

$O(\log(n))$

$h$ $O(\log(n))$

二叉树12:平衡二叉树

leetcode110


xxxxxxxxxx
20
1
class Solution {
2
public:
3
    bool isBalanced(TreeNode* root) 
4
    {
5
        bool ret=true;
6
        function<int(TreeNode*)>depth=[&](TreeNode* head)
7
        {
8
            if(!ret)
9
                return -1;
10
            if(head==nullptr)
11
                return 0;
12
            int ld=depth(head->left);
13
            int rd=depth(head->right);
14
            ret&=abs(ld-rd)<2;
15
            return max(ld,rd)+1;
16
        };
17
        depth(root);
18
        return ret;
19
    }
20
};

二叉树13：二叉树的所有路径

leetcode257

回溯法+dfs

使用to_string()函数(包含于头文件#include<string>),快速将整数转化为字符串


xxxxxxxxxx
28
1
class Solution {
2
public:
3
    vector<string> binaryTreePaths(TreeNode* root) 
4
    {
5
        vector<string>ret;
6
        string str;
7
        function<void(TreeNode*)>dfs=[&](TreeNode* cur)
8
        {
9
            string tmp=to_string(cur->val);
10
            if(cur!=root)
11
                str+="->";
12
            str+=tmp;
13
            if(cur->left==nullptr&&cur->right==nullptr)
14
            {
15
                ret.emplace_back(str);
16
                str=str.substr(0,max<int>(0,str.size()-2-tmp.size()));
17
                return;
18
            }
19
            if(cur->left!=nullptr)
20
                dfs(cur->left);
21
            if(cur->right!=nullptr)
22
                dfs(cur->right);
23
            str=str.substr(0,max<int>(0,str.size()-2-tmp.size()));
24
        };
25
        dfs(root);
26
        return ret;
27
    }
28
};

二叉树15:左叶子之和

leetcode404

这题还挺简单的😏


xxxxxxxxxx
22
1
class Solution {
2
public:
3
    int sumOfLeftLeaves(TreeNode* root) 
4
    {
5
        int ret=0;
6
        //tag=1时表示为左孩子
7
        function<void(TreeNode*,int)>dfs=[&](TreeNode* cur,int tag) 
8
        {
9
            if(tag==1&&cur->left==nullptr&&cur->right==nullptr)
10
            {
11
                ret+=cur->val;
12
                return;
13
            }
14
            if(cur->left!=nullptr)
15
                dfs(cur->left,1);
16
            if(cur->right!=nullptr)
17
                dfs(cur->right,0);
18
        };
19
        dfs(root,0);
20
        return ret;
21
    }
22
};

二叉树16:找树左下角的值

leetcode513

方法1：失败案例（原因：利用对于完全二叉树的节点编号解题，编号过大造成溢出）

idx的意义是节点在对应完全二叉树中的编号n

$h=\lfloor\log_2n\rfloor+1$

$n_左=n<<1$

$n_右=(n<<1)+1$


xxxxxxxxxx
36
1
using ll = unsigned long long; 
2
class Solution {
3
public:
4
    int findBottomLeftValue(TreeNode* root) 
5
    {
6
        //idx的意义是节点在对应完全二叉树中的编号
7
        int max_depth=1;
8
        int ret=-1;
9
        ll ret_idx=0;//越小越好
10
        function<void(TreeNode*,int)>dfs=[&](TreeNode* cur,ll idx)
11
        {
12
            if(cur->left==nullptr&&cur->right==nullptr)
13
            {
14
                int depth=(int)(log(idx)/log(2))+1;
15
                max_depth=max(max_depth,depth);
16
                if(depth==max_depth)
17
                {
18
                    if(ret_idx<(1<<(depth-1)))
19
                        ret_idx=(1<<(depth))-1;
20
                    if(idx<=ret_idx)
21
                    {
22
                        ret_idx=idx;
23
                        ret=cur->val;
24
                    }
25
                }
26
                return;
27
            }
28
            if(cur->left!=nullptr)
29
                dfs(cur->left,idx<<1);
30
            if(cur->right!=nullptr)
31
                dfs(cur->right,(idx<<1)+1);
32
        };
33
        dfs(root,1);
34
        return ret;
35
    }
36
};

方法2: 乖乖用层序遍历,不整花里胡哨的方法才能AC


xxxxxxxxxx
25
1
class Solution {
2
public:
3
    int findBottomLeftValue(TreeNode* root) 
4
    {
5
        int max_depth=0;
6
        int ret=-1;
7
        queue<pair<TreeNode*,int>>que;
8
        que.push({root,1});
9
        while(!que.empty())
10
        {
11
            auto cur=que.front();
12
            que.pop();
13
            if(cur.second>max_depth)
14
            {
15
                max_depth=cur.second;
16
                ret=cur.first->val;
17
            }
18
            if(cur.first->left!=nullptr)
19
                que.push({cur.first->left,cur.second+1});
20
            if(cur.first->right!=nullptr)
21
                que.push({cur.first->right,cur.second+1});
22
        }
23
        return ret;
24
    }
25
};

方法3:整点花里胡哨的,用回溯法

利用性质: 在深度优先搜索中,同一层位于左侧的节点总是最先被搜索到


xxxxxxxxxx
26
1
class Solution {
2
public:
3
    int findBottomLeftValue(TreeNode* root) 
4
    {
5
        int ret=-1;
6
        int max_depth=0;
7
        function<void(TreeNode*,int)>dfs=[&](TreeNode* cur,int depth)
8
        {
9
            if(cur->left==nullptr&&cur->right==nullptr)
10
            {
11
                if(depth>max_depth)
12
                {
13
                    max_depth=depth;
14
                    ret=cur->val;
15
                }
16
                return;
17
            }
18
            if(cur->left!=nullptr)
19
                dfs(cur->left,depth+1);
20
            if(cur->right!=nullptr)
21
                dfs(cur->right,depth+1);
22
        };
23
        dfs(root,1);
24
        return ret;
25
    }
26
};

二叉树17:路径总和

leetcode112路径总和

简单题,回溯解决,大佬可以跳过


xxxxxxxxxx
34
1
class Solution {
2
public:
3
    bool hasPathSum(TreeNode* root, int targetSum) 
4
    {
5
        if(root==nullptr)
6
            return false;
7
        int add=root->val;
8
        bool flag=false;
9
        function<void(TreeNode*)>dfs=[&](TreeNode* cur)
10
        {
11
            if(flag)
12
                return;
13
            if(cur->left==nullptr&&cur->right==nullptr)
14
            {
15
                if(add==targetSum)
16
                    flag=true;
17
            }
18
            if(cur->left!=nullptr)
19
            {
20
                add+=cur->left->val;
21
                dfs(cur->left);
22
                add-=cur->left->val;
23
            }
24
            if(cur->right!=nullptr)
25
            {
26
                add+=cur->right->val;
27
                dfs(cur->right);
28
                add-=cur->right->val;
29
            }
30
        };
31
        dfs(root);
32
        return flag;
33
    }
34
};

leetcode113路径总和II

还是回溯,上面的代码稍微改动即可


xxxxxxxxxx
39
1
class Solution {
2
public:
3
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) 
4
    {
5
        vector<vector<int>>ret;
6
        vector<int>vec;
7
        if(root==nullptr)
8
            return ret;
9
        vec.emplace_back(root->val);
10
        int add=root->val;
11
        function<void(TreeNode*)>dfs=[&](TreeNode* cur)
12
        {
13
            if(cur->left==nullptr&&cur->right==nullptr)
14
            {
15
                if(add==targetSum)
16
                    ret.emplace_back(vec);
17
                return;
18
            }
19
            if(cur->left!=nullptr)
20
            {
21
                add+=cur->left->val;
22
                vec.emplace_back(cur->left->val);
23
                dfs(cur->left);
24
                vec.pop_back();
25
                add-=cur->left->val;
26
            }
27
            if(cur->right!=nullptr)
28
            {
29
                add+=cur->right->val;
30
                vec.emplace_back(cur->right->val);
31
                dfs(cur->right);
32
                vec.pop_back();
33
                add-=cur->right->val;
34
            }
35
        };
36
        dfs(root);
37
        return ret;
38
    }
39
};

二叉树18:从中序与后序遍历序列构造二叉树, 从前序与中序遍历序列构造二叉树

leetcode106从中序与后序遍历序列构造二叉树

回溯法,有点复杂


xxxxxxxxxx
14
1
class Solution {
2
public:
3
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
4
    {
5
        function<TreeNode*(int,int,int,int)>dfs=[&](int ileft,int iright,int pleft,int pright)
6
        {
7
            if(ileft>iright||pleft>pright)
8
                return (TreeNode*)nullptr;
9
            int igap=find(inorder.begin()+ileft,inorder.begin()+iright+1,postorder[pright])-inorder.begin();
10
            return new TreeNode(postorder[pright],dfs(ileft,igap-1,pleft,pleft+igap-ileft-1),dfs(igap+1,iright,pleft+igap-ileft,pright-1));
11
        };
12
        return dfs(0,inorder.size()-1,0,postorder.size()-1);
13
    }
14
};

leetcode105 从前序与中序遍历序列构造二叉树

和上题一样的思路


xxxxxxxxxx
14
1
class Solution {
2
public:
3
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
4
    {
5
        function<TreeNode*(int,int,int,int)>dfs=[&](int pl,int pr,int il,int ir)
6
        {
7
            if(pl>pr||il>ir)
8
                return (TreeNode*)nullptr;
9
            int gap=find(inorder.begin()+il,inorder.begin()+ir+1,preorder[pl])-inorder.begin();
10
            return new TreeNode(preorder[pl],dfs(pl+1,gap-il+pl,il,gap-1),dfs(gap-il+pl+1,pr,gap+1,ir));
11
        };
12
        return dfs(0,preorder.size()-1,0,inorder.size()-1);
13
    }
14
};

二叉树19:最大二叉树

leetcode654


xxxxxxxxxx
22
1
class Solution {
2
public:
3
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) 
4
    {
5
        function<TreeNode*(int,int)>dfs=[&](int le,int ri)
6
        {
7
            if(le>ri)
8
                return (TreeNode*)nullptr;
9
            int max_element=0x80000000,max_index=-1;
10
            for(int i=le;i<=ri;++i)
11
            {
12
                if(nums[i]>max_element)
13
                {
14
                    max_index=i;
15
                    max_element=nums[i];
16
                }
17
            }
18
            return new TreeNode(max_element,dfs(le,max_index-1),dfs(max_index+1,ri));
19
        };
20
        return dfs(0,nums.size()-1);
21
    }
22
};

二叉树21:合并二叉树

leetcode617

一样的回溯思路


xxxxxxxxxx
18
1
class Solution {
2
public:
3
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) 
4
    {
5
        function<TreeNode*(TreeNode*,TreeNode*)>dfs=[&](TreeNode* p1,TreeNode* p2)
6
        {
7
            if(p1!=nullptr&&p2!=nullptr)
8
                return new TreeNode(p1->val+p2->val,dfs(p1->left,p2->left),dfs(p1->right,p2->right));
9
            if(p2==nullptr&&p1!=nullptr)
10
                return new TreeNode(p1->val,dfs(p1->left,nullptr),dfs(p1->right,nullptr));
11
            if(p1==nullptr&&p2!=nullptr)
12
                return new TreeNode(p2->val,dfs(nullptr,p2->left),dfs(nullptr,p2->right));
13
            return (TreeNode*)nullptr;
14
        };
15
        TreeNode* p1=root1,*p2=root2;
16
        return dfs(p1,p2);
17
    }
18
};

二叉树22:二叉搜索树中的搜索

leetcode700

简单题,大佬请跳过


xxxxxxxxxx
17
1
class Solution {
2
public:
3
    TreeNode* searchBST(TreeNode* root, int val) 
4
    {
5
        TreeNode* p=root;
6
        while(p!=nullptr)
7
        {
8
            if(val==p->val)
9
                return p;
10
            else if(val<p->val)
11
                p=p->left;
12
            else
13
                p=p->right;
14
        }
15
        return nullptr;
16
    }
17
};

二叉树23:验证二叉搜索树

leetcode98

别小看这题,坑巨多


xxxxxxxxxx
33
1
class Solution {
2
public:
3
    bool isValidBST(TreeNode* root) 
4
    {
5
        bool ret=true;
6
        int downinf=1,upinf=1;
7
        function<void(TreeNode*,int,int)>dfs=[&](TreeNode* cur,int up,int down)
8
        {
9
            if(!ret||cur==nullptr)
10
                return;
11
            if(cur->val<=down&&downinf==0||cur->val>=up&&upinf==0)
12
                ret=false;
13
            if(upinf==1)
14
            {
15
                upinf=0;
16
                dfs(cur->left,cur->val,down);
17
                upinf=1;
18
            }
19
            else
20
                dfs(cur->left,cur->val,down);
21
            if(downinf==1)
22
            {
23
                downinf=0;
24
                dfs(cur->right,up,cur->val);
25
                downinf=1;
26
            }
27
            else
28
                dfs(cur->right,up,cur->val);
29
        };
30
        dfs(root,0,0);
31
        return ret;
32
    }
33
};

二叉树24:二叉搜索树的最小绝对差

leetcode530

相当于求二叉树中序遍历序列相邻元素的最小绝对差


xxxxxxxxxx
19
1
class Solution {
2
public:
3
    int getMinimumDifference(TreeNode* root) 
4
    {
5
        int last=-1000000;
6
        int ret=0x7fffffff;
7
        function<void(TreeNode*)>dfs=[&](TreeNode* cur)//中序遍历
8
        {
9
            if(cur==nullptr)
10
                return;
11
            dfs(cur->left);
12
            ret=min(ret,abs(cur->val-last));
13
            last=cur->val;
14
            dfs(cur->right);
15
        };
16
        dfs(root);
17
        return ret;
18
    }
19
};

二叉树25：二叉搜索树中的众数

leetcode501

采用中序遍历就行


xxxxxxxxxx
53
1
class Solution {
2
public:
3
    vector<int> findMode(TreeNode* root) 
4
    {
5
        int pre=-200000;
6
        int cnt=1,ret=1;
7
        vector<int>vec;
8
        function<void(TreeNode*)>dfs=[&](TreeNode* cur)
9
        {
10
            if(cur==nullptr)
11
                return;
12
            dfs(cur->left);
13
            if(cur->val==pre)
14
            {
15
                ++cnt;
16
            }
17
            else if(pre!=-200000)
18
            {
19
                if(cnt>ret)
20
                {
21
                    vec.resize(0);
22
                    vec.emplace_back(pre);
23
                    ret=cnt;
24
                }
25
                else if(cnt==ret)
26
                {
27
                    vec.emplace_back(pre);
28
                }
29
                cnt=1;
30
                pre=cur->val;
31
            }
32
            else
33
            {
34
                cnt=1;
35
                pre=cur->val;
36
            }
37
            dfs(cur->right);
38
        };
39
        dfs(root);
40
        if(cnt>ret)
41
        {
42
            vec.resize(0);
43
            vec.emplace_back(pre);
44
            ret=cnt;
45
        }
46
        else if(cnt==ret)
47
        {
48
            vec.emplace_back(pre);
49
        }
50
        cnt=1;
51
        return vec;
52
    }
53
};

二叉树26:二叉树的最近公共祖先

leetcode236

直接回溯


xxxxxxxxxx
28
1
class Solution {
2
public:
3
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
4
    {
5
        TreeNode* ret=nullptr;
6
        int depth=-1;
7
        function<int(TreeNode*,int)>dfs=[&](TreeNode* cur,int dep)
8
        {
9
            if(cur==nullptr)
10
                return 0;
11
            int status=0;
12
            if(cur==p)
13
                status|=2;
14
            else if(cur==q)
15
                status|=1;
16
            status|=dfs(cur->left,dep+1);
17
            status|=dfs(cur->right,dep+1);
18
            if(status==3&&dep>depth)
19
            {
20
                depth=dep;
21
                ret=cur;
22
            }
23
            return status;
24
        };
25
        dfs(root,0);
26
        return ret;
27
    }
28
};

二叉树28:二叉搜索树的最近公共祖先

leetcode235

和上一题差不多,这题是二叉搜索树,可以利用性质简化

用指针t从根节点开始采用二分搜索,直到发现t==p||t==q,或者p和q分别位于t两侧


xxxxxxxxxx
19
1
class Solution {
2
public:
3
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
4
    {
5
        TreeNode* t=root;
6
        while(t!=nullptr)
7
        {
8
            if(t==p||t==q)
9
                return t;
10
            if(t->val>p->val&&t->val>q->val)
11
                t=t->left;
12
            else if(t->val<p->val&&t->val<q->val)
13
                t=t->right;
14
            else
15
                return t;
16
        }
17
        return nullptr;
18
    }
19
};

二叉树29:二叉搜索树的插入操作

leetcode701

简单题,大佬可跳过


xxxxxxxxxx
33
1
class Solution {
2
public:
3
    TreeNode* insertIntoBST(TreeNode* root, int val) 
4
    {
5
        TreeNode* p=root;
6
        if(p==nullptr)
7
            return new TreeNode(val);
8
        while(1)
9
        {
10
            if(val>p->val)
11
            {
12
                if(p->right!=nullptr)
13
                    p=p->right;
14
                else
15
                {
16
                    p->right=new TreeNode(val);
17
                    return root;                    
18
                }
19
            }
20
            else
21
            {
22
                if(p->left!=nullptr)
23
                    p=p->left;
24
                else
25
                {
26
                    p->left=new TreeNode(val);
27
                    return root;
28
                }
29
            }
30
        }
31
        return root;
32
    }
33
};

二叉树30:删除二叉搜索树中的节点

leetcode450


xxxxxxxxxx
53
1
class Solution {
2
public:
3
    TreeNode* deleteNode(TreeNode* root, int key) 
4
    {
5
        TreeNode* dummyhead=new TreeNode(0,root,nullptr);
6
        TreeNode* pre=dummyhead;
7
        TreeNode* cur=root;
8
        while(cur!=nullptr&&cur->val!=key)
9
        {
10
            pre=cur;
11
            if(cur->val>key)
12
                cur=cur->left;
13
            else
14
                cur=cur->right;
15
        }
16
        if(cur==nullptr)
17
        {
18
            delete dummyhead;
19
            return root;
20
        }
21
        if(cur->left==nullptr)
22
        {
23
            if(pre->left==cur)
24
                pre->left=cur->right;
25
            else
26
                pre->right=cur->right;
27
        }
28
        else if(cur->right==nullptr)
29
        {
30
            if(pre->left==cur)
31
                pre->left=cur->left;
32
            else
33
                pre->right=cur->left;
34
        }
35
        else
36
        {
37
            TreeNode* tmp=cur->left->right;
38
            TreeNode* p=cur->right;
39
            cur->left->right=cur->right;
40
            if(pre->left==cur)
41
                pre->left=cur->left;
42
            else
43
                pre->right=cur->left;
44
            while(p->left!=nullptr)
45
                p=p->left;
46
            p->left=tmp;
47
        }
48
        delete cur;
49
        TreeNode* ret=dummyhead->left;
50
        delete dummyhead;
51
        return ret;
52
    }
53
};

回溯2：组合

leetcode77

C++:


xxxxxxxxxx
27
1
class Solution {
2
public:
3
    vector<vector<int>> combine(int n, int k) 
4
    {
5
        vector<vector<int>>ret;
6
        vector<int>sel;
7
        sel.reserve(n);
8
        function<void(int)> dfs=[&](int idx)
9
        {
10
            if(n-idx+1<k-sel.size())//剪枝
11
                return;
12
            if(idx>n+1)//递归上限
13
                return;
14
            if(sel.size()==k)
15
            {
16
                ret.emplace_back(sel);
17
                return;
18
            }
19
            dfs(idx+1);//不取当前数字
20
            sel.emplace_back(idx);
21
            dfs(idx+1);//取当前数字
22
            sel.pop_back();
23
        };
24
        dfs(1);
25
        return ret;
26
    }
27
};

python: 要注意几个global的使用


xxxxxxxxxx
26
1
num=0  # 统计已经加入数组arr的元素数量
2
ret=[]
3
arr=[]
4
class Solution:
5
    def combine(self, n: int, k: int) -> List[List[int]]:
6
        global num,ret,arr
7
        ret=[]
8
        arr=[]
9
        num=0
10
        def dfs(idx: int):
11
            global num,ret,arr
12
            if num>k:
13
                return
14
            if idx==n+1:
15
                if num==k:
16
                    ret.append(arr.copy())
17
                return
18
            dfs(idx+1)
19
            num+=1
20
            arr.append(idx)
21
            dfs(idx+1)
22
            num-=1
23
            arr.pop(num)
24
        dfs(1)
25
        return ret
26

回溯4:组合总和III

leetcode216


xxxxxxxxxx
28
1
class Solution {
2
public:
3
    vector<vector<int>> combinationSum3(int k, int n) 
4
    {
5
        vector<vector<int>>ret;
6
        vector<int>sel;
7
        sel.reserve(k);
8
        int add=0;
9
        function<void(int)>dfs=[&](int idx)
10
        {
11
            if(idx>10)
12
                return;
13
            if(add==n&&sel.size()==k)
14
            {
15
                ret.emplace_back(sel);
16
                return;
17
            }
18
            dfs(idx+1);
19
            add+=idx;
20
            sel.emplace_back(idx);
21
            dfs(idx+1);
22
            add-=idx;
23
            sel.pop_back();
24
        };
25
        dfs(1);
26
        return ret;
27
    }
28
};

回溯5:电话号码的字母组合

leetcode17

方法1: 两层for循环模拟枚举


xxxxxxxxxx
34
1
class Solution {
2
public:
3
    vector<string> letterCombinations(string digits) 
4
    {
5
        vector<string> str={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
6
        vector<string> vec;
7
        for(int i=0;i<digits.size();++i)
8
        {
9
            int idx=digits[i]-'0';
10
            if(i==0)
11
            {
12
                for(int j=0;j<str[idx].size();++j)
13
                {
14
                    vec.emplace_back(str[idx].substr(j,1));
15
                }
16
            }
17
            else
18
            {
19
                int j=0;
20
                for(;j<vec.size()&&vec[j].size()<=i;++j)
21
                {
22
                    for(auto ch:str[idx])
23
                    {
24
                        string tmp=vec[j];
25
                        tmp+=ch;
26
                        vec.emplace_back(tmp);
27
                    }
28
                }
29
                vec.erase(vec.begin(),vec.begin()+j);
30
            }
31
        }
32
        return vec;
33
    }
34
};

方法2:递归回溯


xxxxxxxxxx
27
1
class Solution {
2
public:
3
    vector<string> letterCombinations(string digits) 
4
    {
5
        vector<vector<char>>vec={{},{},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
6
        vector<string>ret;
7
        string s;
8
        function<void(int)>dfs=[&](int idx)
9
        {
10
            if(idx==digits.size())
11
            {
12
                if(s.size()!=0)
13
                    ret.emplace_back(s);
14
                return;
15
            }
16
            vector<char>&tmp=vec[digits[idx]-'0'];
17
            for(char& ch:tmp)
18
            {
19
                s.push_back(ch);
20
                dfs(idx+1);
21
                s.pop_back();
22
            }
23
        };
24
        dfs(0);
25
        return ret;
26
    }
27
};

回溯7:组合总和

leetcode39


xxxxxxxxxx
39
1
class Solution {
2
public:
3
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
4
    {
5
        vector<vector<int>>ret;
6
        vector<int>vec;
7
        int add=0;
8
        function<void(int)>dfs=[&](int idx)
9
        {
10
            if(idx==candidates.size())
11
            {
12
                if(add==target)
13
                    ret.emplace_back(vec);
14
                return;
15
            }
16
            dfs(idx+1);
17
            int cnt=0;
18
            while(1)
19
            {
20
                if(add+candidates[idx]<=target)
21
                {
22
                    add+=candidates[idx];
23
                    vec.emplace_back(candidates[idx]);
24
                    ++cnt;
25
                    dfs(idx+1);                    
26
                }
27
                else
28
                    break;
29
            }
30
            for(int i=0;i<cnt;++i)
31
            {
32
                add-=candidates[idx];
33
                vec.pop_back();
34
            }
35
        };
36
        dfs(0);
37
        return ret;
38
    }
39
};

回溯8:组合总和II

leetcode40


xxxxxxxxxx
33
1
class Solution {
2
public:
3
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
4
    {
5
        vector<vector<int>>ret;
6
        vector<int>vec;
7
        int add=0;
8
        sort(candidates.begin(),candidates.end());//避免出现重复的组合
9
        function<void(int)>dfs=[&](int idx)
10
        {
11
            if(add>target)
12
                return;
13
            if(add==target)
14
            {
15
                ret.emplace_back(vec);
16
                return;
17
            }
18
            if(idx==candidates.size())
19
                return;
20
            vec.emplace_back(candidates[idx]);
21
            add+=candidates[idx];
22
            dfs(idx+1);
23
            vec.pop_back();
24
            add-=candidates[idx];
25
            int i=idx+1;
26
            while(i<candidates.size()&&candidates[i]==candidates[i-1])
27
                ++i;
28
            dfs(i);
29
        };
30
        dfs(0);
31
        return ret;
32
    }
33
};

回溯9：分割回文串

leetcode131


xxxxxxxxxx
52
1
class Solution {
2
public:
3
    int len;
4
    string str;
5
    vector<vector<string>> ret;
6
    bool ispalind(string s)
7
    {
8
        int slen=s.size();
9
        int i=0,j=slen-1;
10
        for(;i<j;++i,--j)
11
        {
12
            if(s[i]!=s[j])
13
                return false;
14
        }
15
        return true;
16
    }
17
    void dfs(int idx,vector<int>punc)
18
    {
19
        if(idx==len)
20
        {
21
            vector<string> tmp;
22
            int last=0;
23
            for(int i=1;i<=punc.size();++i)
24
            {
25
                if(i==punc.size()||punc[i]==1)
26
                {
27
                    string st=str.substr(last,i-last);
28
                    if(!ispalind(st))
29
                        return;
30
                    tmp.emplace_back(st);
31
                    last=i;
32
                }
33
            }
34
            ret.emplace_back(tmp);
35
            return;
36
        }
37
        else
38
        {
39
            dfs(idx+1,punc);
40
            punc[idx]=1;
41
            dfs(idx+1,punc);
42
        }
43
    }
44
    vector<vector<string>> partition(string s) 
45
    {
46
        len=s.size();
47
        str=s;
48
        vector<int>punc(len);
49
        dfs(1,punc);
50
        return ret;
51
    }
52
};

回溯10：复原IP地址

leetcode93


xxxxxxxxxx
43
1
class Solution {
2
public:
3
    vector<string> restoreIpAddresses(string s) 
4
    {
5
        int n=s.size();
6
        string tmp;
7
        vector<string>ret;
8
        int cnt=0;
9
        function<void(int)>dfs=[&](int i)
10
        {
11
            if(cnt==4||i==n)
12
            {
13
                if(cnt==4&&i==n)
14
                    ret.emplace_back(tmp);
15
                return;
16
            }
17
            for(int j=i;j<n&&j<i+3;++j)
18
            {
19
                string add=s.substr(i,j-i+1);
20
                int num=stoi(add);
21
                if(num<=255&&s[i]!='0'||s[i]=='0'&&j==i)
22
                {
23
                    int flag=0;
24
                    if(tmp.size()!=0)
25
                    {
26
                        tmp+='.';
27
                        flag=1;
28
                    }
29
                    tmp+=add;
30
                    ++cnt;
31
                    dfs(j+1);
32
                    --cnt;
33
                    if(flag)
34
                        tmp.erase(tmp.size()-add.size()-1,add.size()+1);
35
                    else
36
                        tmp.erase(tmp.size()-add.size(),add.size());
37
                }
38
            }
39
        };
40
        dfs(0);
41
        return ret;
42
    }
43
};

回溯11：子集

leetcode78


xxxxxxxxxx
25
1
class Solution {
2
public:
3
    vector<vector<int>> ret;
4
    vector<int>num;
5
    int n;
6
    void make(vector<int> tem,int p)
7
    {
8
        if(p==n)
9
        {
10
            ret.push_back(tem);
11
            return;
12
        }
13
        make(tem,p+1);
14
        tem.push_back(num[p]);
15
        make(tem,p+1);
16
    }
17
    vector<vector<int>> subsets(vector<int>& nums) 
18
    {
19
        n=nums.size();
20
        num=nums;
21
        vector<int> tem;
22
        make(tem,0);
23
        return ret;
24
    }
25
};

回溯13：子集II

leetcode90


xxxxxxxxxx
26
1
class Solution {
2
public:
3
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
4
    {
5
        vector<vector<int>>ret;
6
        vector<int>tmp;
7
        sort(nums.begin(),nums.end());
8
        int n=nums.size();
9
        function<void(int)>dfs=[&](int idx)
10
        {
11
            if(idx==n)
12
            {
13
                ret.emplace_back(tmp);
14
                return;
15
            }
16
            tmp.emplace_back(nums[idx]);
17
            dfs(idx+1);
18
            tmp.pop_back();
19
            while(idx+1<n&&nums[idx+1]==nums[idx])
20
                ++idx;
21
            dfs(idx+1);
22
        };
23
        dfs(0);
24
        return ret;
25
    }
26
};

回溯14：递增子序列

leetcode491


xxxxxxxxxx
33
1
class Solution {
2
public:
3
    vector<vector<int>> findSubsequences(vector<int>& nums) 
4
    {
5
        int n=nums.size();
6
        vector<vector<int>>ret;
7
        vector<int>tmp;
8
        function<void(int)>dfs=[&](int idx)
9
        {
10
            if(idx==n)
11
            {
12
                if(tmp.size()>=2)
13
                    ret.emplace_back(tmp);
14
                return;
15
            }
16
            unordered_map<int,int>hash;
17
            for(int i=idx;i<n;++i)
18
            {
19
                if(hash[nums[i]]==0&&(tmp.size()==0||nums[i]>=tmp.back()))
20
                {
21
                    hash[nums[i]]=1;
22
                    tmp.emplace_back(nums[i]);
23
                    dfs(i+1);
24
                    tmp.pop_back();
25
                }
26
            }
27
            if(tmp.size()>=2)
28
                ret.emplace_back(tmp);
29
        };
30
        dfs(0);
31
        return ret;
32
    }
33
};

回溯15：全排列

leetcode46


xxxxxxxxxx
30
1
class Solution {
2
public:
3
    vector<vector<int>> permute(vector<int>& nums) 
4
    {
5
        vector<vector<int>> ret;
6
        vector<int>isvalid(nums.size(),0);
7
        vector<int>cur;
8
        auto dfs=[&]()
9
        {
10
            if(cur.size()==nums.size())
11
            {
12
                ret.emplace_back(cur);
13
                return;
14
            }
15
            for(int i=0;i<nums.size();++i)
16
            {
17
                if(isvalid[i]==0)
18
                {
19
                    cur.emplace_back(nums[i]);
20
                    isvalid[i]=1;
21
                    dfs();
22
                    cur.pop_back();
23
                    isvalid[i]=0;
24
                }
25
            }
26
        };
27
        dfs();
28
        return ret;
29
    }
30
};

回溯16：全排列II

leetcode47

方法1：在得到全排列数组后进行整体去重


xxxxxxxxxx
43
1
using ll=long long;
2
class Solution {
3
public:
4
    vector<vector<int>> permuteUnique(vector<int>& nums) 
5
    {
6
        vector<ll>quan(nums.size());
7
        quan[0]=1;
8
        for(int i=1;i<nums.size();++i)
9
            quan[i]=quan[i-1]*11;
10
        unordered_map<ll,int>hash;
11
        vector<int>vec(nums.size());
12
        vector<int>cur;
13
        vector<vector<int>>ret;
14
        ll key=0;
15
        function<void(int)>dfs=[&](int idx)
16
        {
17
            if(idx==nums.size())
18
            {
19
                if(hash[key]==0)
20
                {
21
                    hash[key]=1;
22
                    ret.emplace_back(cur);
23
                }
24
                return;
25
            }
26
            for(int i=0;i<nums.size();++i)
27
            {
28
                if(vec[i]==0)
29
                {
30
                    vec[i]=1;
31
                    cur.emplace_back(nums[i]);
32
                    key+=quan[idx]*nums[i];
33
                    dfs(idx+1);
34
                    key-=quan[idx]*nums[i];
35
                    vec[i]=0;
36
                    cur.pop_back();
37
                }
38
            }
39
        };
40
        dfs(0);
41
        return ret;
42
    }
43
};

60ms,8.8MB

方法2：在递归的同一层内避免插入相同元素到数组中，有效避免出现重复


xxxxxxxxxx
36
1
class Solution {
2
public:
3
    vector<vector<int>> permuteUnique(vector<int>& nums) 
4
    {
5
        int n=nums.size();
6
        vector<int>isvisited(n);
7
        vector<int>tmp;
8
        vector<vector<int>>ret;
9
        function<void(int)>dfs=[&](int idx)
10
        {
11
            if(idx==n)
12
            {
13
                ret.emplace_back(tmp);
14
                return;
15
            }
16
            unordered_map<int,int>hash;
17
            for(int i=0;i<n;++i)
18
            {
19
                if(isvisited[i]==0)
20
                {
21
                    if(hash[nums[i]]==0)
22
                    {
23
                        hash[nums[i]]=1;
24
                        isvisited[i]=1;
25
                        tmp.emplace_back(nums[i]);
26
                        dfs(idx+1);
27
                        tmp.pop_back();
28
                        isvisited[i]=0;
29
                    }
30
                }
31
            }
32
        };
33
        dfs(0);
34
        return ret;
35
    }
36
};

8ms,10.9MB

回溯19：重新安排行程

leetcode332


xxxxxxxxxx
41
1
class Solution {
2
public:
3
    vector<string> findItinerary(vector<vector<string>>& tickets) 
4
    {
5
        int n=tickets.size();
6
        sort(tickets.begin(),tickets.end(),[&](vector<string>&a,vector<string>&b){return a[1]<b[1];});
7
        string loca="JFK";
8
        vector<int>isUsed(n);
9
        vector<string>ret;
10
        vector<string>ret1;
11
        ret.emplace_back(loca);
12
        int flag=0;
13
        function<void(int)>dfs=[&](int idx)
14
        {
15
            if(flag)
16
                return;
17
            if(idx==n)
18
            {
19
                ret1=ret;
20
                flag=1;
21
                return;
22
            }
23
            for(int i=0;i<n;++i)
24
            {
25
                if(tickets[i][0]==loca&&isUsed[i]==0)
26
                {
27
                    isUsed[i]=1;
28
                    string tmp=loca;
29
                    loca=tickets[i][1];
30
                    ret.emplace_back(loca);
31
                    dfs(idx+1);
32
                    ret.pop_back();
33
                    loca=tmp;
34
                    isUsed[i]=0;
35
                }
36
            }
37
        };
38
        dfs(0);
39
        return ret1;
40
    }
41
};

回溯20：N皇后

leetcode51


xxxxxxxxxx
58
1
class Solution {
2
public:
3
    vector<vector<string>> solveNQueens(int n) 
4
    {
5
        vector<vector<string>>ret;
6
        vector<string>graph(n);
7
        for(auto& _vec:graph)
8
            _vec.assign(n,'.');
9
        vector<int>row(n);
10
        function<void(int)>dfs=[&](int col)
11
        {
12
            if(col==n)
13
            {
14
                ret.emplace_back(graph);
15
                return;
16
            }
17
            for(int i=0;i<n;++i)
18
            {
19
                if(row[i]!=0)
20
                    continue;
21
                int flag=0;
22
                for(int j=0;j<n;++j)
23
                {
24
                    int k=i+col-j;
25
                    if(k<0||k>=n)
26
                        continue;
27
                    if(graph[j][k]=='Q')
28
                    {
29
                        flag=1;
30
                        break;
31
                    }
32
                }
33
                if(flag==1)
34
                    continue;
35
                for(int j=0;j<n;++j)
36
                {
37
                    int k=j+col-i;
38
                    if(k<0||k>=n)
39
                        continue;
40
                    if(graph[j][k]=='Q')
41
                    {
42
                        flag=1;
43
                        break;
44
                    }
45
                }
46
                if(flag==1)
47
                    continue;
48
                row[i]=1;
49
                graph[i][col]='Q';
50
                dfs(col+1);
51
                row[i]=0;
52
                graph[i][col]='.';
53
            }
54
        };
55
        dfs(0);
56
        return ret;
57
    }
58
};

回溯21：解数独

leetcode37

数独棋盘：

	0	1	2	3	4	5	6	7	8
0
1
2
3
4
5
6
7
8

$3\times 3$ 宫：比较x/3*10+y/3的大小


xxxxxxxxxx
59
1
class Solution {
2
public:
3
    void solveSudoku(vector<vector<char>>& board) 
4
    {
5
        int flag=0;//已经填好的标记
6
        function<void(int,int)>dfs=[&](int x,int y)
7
        {
8
            if(flag)
9
                return;
10
            if(x==9)
11
            {
12
                flag=1;
13
                return;
14
            }
15
            if(board[x][y]=='.')
16
            {
17
                vector<int>isvalid(10);
18
                for(int i=0;i<=8;++i)//处理同行同列
19
                {
20
                    if(board[i][y]!='.')
21
                        isvalid[board[i][y]-'0']=1;
22
                    if(board[x][i]!='.')
23
                        isvalid[board[x][i]-'0']=1;
24
                }
25
                for(int i=0;i<3;++i)
26
                {
27
                    for(int j=0;j<3;++j)
28
                    {
29
                        if(board[x/3*3+i][y/3*3+j]!='.')
30
                            isvalid[board[x/3*3+i][y/3*3+j]-'0']=1;
31
                    }
32
                }
33
                for(int i=1;i<=9;++i)
34
                {
35
                    if(isvalid[i]==0)
36
                    {
37
                        board[x][y]=i+'0';
38
                        if(y==8)//访问下一个格子
39
                            dfs(x+1,0);
40
                        else
41
                            dfs(x,y+1);
42
                        if(flag==1)
43
                            return;
44
                        else
45
                            board[x][y]='.';
46
                    }
47
                }
48
            }
49
            else
50
            {
51
                if(y==8)//访问下一个格子
52
                    dfs(x+1,0);
53
                else
54
                    dfs(x,y+1);
55
            }
56
        };
57
        dfs(0,0);
58
    }
59
};

贪心2：分发饼干

leetcode455

排序 + 双指针 + 贪心


xxxxxxxxxx
21
1
class Solution {
2
public:
3
    int findContentChildren(vector<int>& g, vector<int>& s) 
4
    {
5
        sort(g.begin(),g.end());
6
        sort(s.begin(),s.end());
7
        int i=0,j=0;
8
        int ret=0;
9
        for(;i<g.size()&&j<s.size();++i)
10
        {
11
            while(j<s.size()&&s[j]<g[i])
12
                ++j;
13
            if(j<s.size()&&s[j]>=g[i])
14
            {
15
                ++j;
16
                ++ret;
17
            }
18
        }
19
        return ret;
20
    }
21
};

贪心3：摆动序列

leetcode376

python:


xxxxxxxxxx
27
1
class Solution:
2
    def wiggleMaxLength(self, nums: List[int]) -> int:
3
        le=len(nums)
4
        i=1
5
        flag=1  # 1表示增，2表示减
6
        ret=1
7
        while i<le and nums[i]==nums[i-1]:
8
            i+=1
9
        if i<le and nums[i]>nums[i-1]:
10
            flag=1
11
        elif i<le:
12
            flag=0
13
        else:
14
            return 1
15
        i=1
16
        while i<le:
17
            if flag==1:
18
                while i<le and nums[i]>=nums[i-1]:
19
                    i+=1
20
                ret+=1
21
                flag=0
22
            else:
23
                while i<le and nums[i]<=nums[i-1]:
24
                    i+=1
25
                ret+=1
26
                flag=1
27
        return ret

贪心4：最大子数组和

leetcode53

这里考虑局部最优解

从左到右遍历一次nums数组，遍历到第i个元素时,add的含义是选择nums[i]的条件下考虑前i个元素的最大子数组和

然后用ret记录add的最大值

C++:


xxxxxxxxxx
13
1
class Solution {
2
public:
3
    int maxSubArray(vector<int>& nums) 
4
    {
5
        int ret=nums[0],add=nums[0];
6
        for(int i=1;i<nums.size();++i)
7
        {
8
            add=max(add+nums[i],nums[i]);
9
            ret=max(ret,add);
10
        }
11
        return ret;
12
    }
13
};

python:


xxxxxxxxxx
8
1
class Solution:
2
    def maxSubArray(self, nums: List[int]) -> int:
3
        add=0
4
        ret=-100000
5
        for num in nums:
6
            add=max(add+num,num)
7
            ret=max(ret,add)
8
        return ret

贪心6:买卖股票的最佳时机 II

leetcode122

动态规划章节也包含了这道题

方法1:贪心

相当于截取prices数组中的所有上升子数组,求出它们的首尾元素之差并求和


xxxxxxxxxx
10
1
int maxProfit(int* prices, int pricesSize)
2
{
3
    int ret=0;
4
    for(int i=1;i<pricesSize;++i)
5
    {
6
        if(prices[i]>prices[i-1])
7
            ret+=prices[i]-prices[i-1];
8
    }
9
    return ret;
10
}

python:


xxxxxxxxxx
9
1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        pre=inf
4
        profit=0
5
        for num in prices:
6
            if num-pre>0:
7
                profit+=num-pre
8
            pre=num
9
        return profit

方法2:奇妙的动态规划

dfs[i][0]表示第i天结束不持有股票的最大利润pair.first

dfs[i][1]表示第i天结束持有股票的最大利润pair.second

C++:一维数组递推


xxxxxxxxxx
16
1
class Solution {
2
public:
3
    int maxProfit(vector<int>& prices) 
4
    {
5
        int len=prices.size();
6
        vector<pair<int,int>> dfs(len);
7
        dfs[0].first=0;
8
        dfs[0].second=-prices[0];
9
        for(int i=1;i<len;++i)
10
        {
11
            dfs[i].first=max(dfs[i-1].first,dfs[i-1].second+prices[i]);
12
            dfs[i].second=max(dfs[i-1].second,dfs[i-1].first-prices[i]);
13
        }
14
            return dfs[len-1].first;
15
    }
16
};

python:将一维数组压缩为更新两个变量


xxxxxxxxxx
10
1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        have=-prices[0]  # 当前持有股票的最大利润
4
        notHave=0  # 当前不持有股票的最大利润
5
        for i in range(1,len(prices)):
6
            tp1=max(have,notHave-prices[i])
7
            tp2=max(notHave,have+prices[i])
8
            have=tp1
9
            notHave=tp2
10
        return notHave

贪心7:跳跃游戏

简单贪心,只需维护bound作为当前能到达的最远位置


xxxxxxxxxx
20
1
bool canJump(int* nums, int numsSize)
2
{
3
    if(numsSize==1)
4
        return true;
5
    for(int i=0;i<numsSize-1;i++)
6
    {
7
        if(nums[i]==0)
8
        {
9
            int p=0;
10
            for(int j=i;j>=0;j--)
11
            {
12
                if(nums[i-j]>j)
13
                    p=1;
14
            }
15
            if(p==0)
16
                return false;
17
        }
18
    }
19
    return true;
20
}

python:


xxxxxxxxxx
8
1
class Solution:
2
    def canJump(self, nums: List[int]) -> bool:
3
        bound=0
4
        for idx,num in enumerate(nums):
5
            if idx>bound:
6
                return False
7
            bound=max(bound,idx+num)
8
        return True

贪心8：跳跃游戏II

leetcode45


xxxxxxxxxx
19
1
int jump(int* nums, int numsSize)
2
{
3
    int dis1=0,dis2=0;
4
    if(numsSize==1)
5
        return 0;
6
    for(int i=1;i<numsSize;i++)
7
    {
8
        int far=0;
9
        for(int j=dis2;j<=dis1;j++)
10
        {
11
            far=far>nums[j]+j?far:nums[j]+j;
12
        }
13
        dis2=dis1+1;
14
        dis1=far;
15
        if(dis1>=numsSize-1)
16
            return i;
17
    }
18
    return 0;
19
}

贪心9:K次取反后最大化的数组和

leetcode1005

你可能都没意识到你用了贪心算法, 就不小心AC了

python:


xxxxxxxxxx
16
1
class Solution:
2
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
3
        nums=sorted(nums)
4
        idx=0
5
        while idx<len(nums) and nums[idx]<0 and k>0:
6
            nums[idx]*=-1
7
            idx+=1
8
            k-=1
9
        if k==0:
10
            return sum(nums)
11
        elif idx==len(nums):
12
            nums[idx-1]*=(-1)**k
13
            return sum(nums)
14
        nums=sorted(nums)
15
        nums[0]*=(-1)**k
16
        return sum(nums)

贪心11: 加油站

leetcode134

难度蹭蹭上涨了

$O(n^2)$ 的暴力解法可以通过,感兴趣的可以试试😉

贪心:

C++:

$O(n)$ $O(n)$


xxxxxxxxxx
35
1
class Solution {
2
public:
3
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
4
    {
5
        int n=gas.size();
6
        vector<int>vec(n);
7
        for(int i=0;i<n;++i)
8
            vec[i]=gas[i]-cost[i];
9
        int begin=0,end=0;//双指针,左闭右闭
10
        int add=0;//当前油箱汽油量
11
        int flag=0;//flag==1代表end已经越过n回到0
12
        while(begin!=end||flag==0)
13
        {
14
            add+=vec[end];
15
            if(add<0)
16
            {
17
                if(flag==1)
18
                    return -1;
19
                add=0;
20
                ++end;
21
                if(end==n)
22
                    return -1;
23
                begin=end;
24
                continue;
25
            }
26
            ++end;
27
            if(end==n)
28
            {
29
                end=0;
30
                flag=1;
31
            } 
32
        }
33
        return begin;
34
    }
35
};

贪心12:分发糖果

leetcode135

方法1:自己的复杂方法

把ratings数组视为一个波, 各个下标处对应的数值为该处波的高度

一次遍历,找到所有的波谷下标装入队列

然后从队列逐个取出下标,从波谷向两侧遍历直到到达波峰, 对于严格上升的点糖果数为上一个位置的糖果数+1,平缓的点糖果数为1

一个位置的糖果数可能被多次计算,取其中的最大值

C++:


xxxxxxxxxx
43
1
class Solution {
2
public:
3
    int candy(vector<int>& ratings) 
4
    {
5
        int n=ratings.size();
6
        if(n==1)
7
            return 1;
8
        queue<int>que;//记录所有波谷的下标
9
        if(ratings[0]<=ratings[1])
10
            que.push(0);
11
        for(int i=1;i<n-1;++i)
12
        {
13
            if(ratings[i-1]>=ratings[i]&&ratings[i]<=ratings[i+1])
14
                que.push(i);
15
        }
16
        if(ratings[n-2]>=ratings[n-1])
17
            que.push(n-1);
18
        vector<int>candy(n,1);
19
        while(!que.empty())
20
        {
21
            int cur=que.front();
22
            que.pop();
23
            candy[cur]=1;
24
            int left=cur-1;
25
            for(;left>=0;--left)
26
            {
27
                if(ratings[left]>ratings[left+1])
28
                    candy[left]=max(candy[left],candy[left+1]+1);
29
                else if(ratings[left]<ratings[left+1])
30
                    break;
31
            }
32
            int right=cur+1;
33
            for(;right<n;++right)
34
            {
35
                if(ratings[right]>ratings[right-1])
36
                    candy[right]=max(candy[right],candy[right-1]+1);
37
                else if(ratings[right]<ratings[right-1])
38
                    break;
39
            }
40
        }
41
        return accumulate(candy.begin(),candy.end(),0);
42
    }
43
};

方法2:大佬们的方法

正反两次遍历

python:


xxxxxxxxxx
11
1
class Solution:
2
    def candy(self, ratings: List[int]) -> int:
3
        n=len(ratings)
4
        candies=[1]*n
5
        for i in range(n):  # 只考虑左孩子比右孩子分数低的情况
6
            if i != 0 and ratings[i]>ratings[i-1]:
7
                candies[i]=max(candies[i],candies[i-1]+1)
8
        for i in range(n-1,-1,-1):  # 只考虑左孩子比右孩子分数高的1情况
9
            if i != n-1 and ratings[i]>ratings[i+1]:
10
                candies[i]=max(candies[i],candies[i+1]+1)
11
        return sum(candies)

贪心13:柠檬水找零

leetcode860

简单模拟就行,用生活经验,有10元就优先用10元找零,5元是万能的

python:


xxxxxxxxxx
19
1
class Solution:
2
    def lemonadeChange(self, bills: List[int]) -> bool:
3
        n5=0  # 5美元钞票数
4
        n10=0  # 10美元钞票数
5
        for bill in bills:
6
            if bill==5:
7
                n5+=1
8
            elif bill==10:
9
                n5-=1
10
                n10+=1
11
            else:
12
                if n10>0:
13
                    n10-=1
14
                    n5-=1
15
                else:
16
                    n5-=3
17
            if n5<0:
18
                return False
19
        return True

贪心14：根据身高重建队列*

leetcode406

有点难😭

搬运自讨论区的精彩解释:https://leetcode.cn/problems/queue-reconstruction-by-height/discussion/comments/1809851

上了第一节体育课，老师给大家排好了体操的队伍，可是大家脑子都很笨，记不清自己在哪，老师说，你就看前面有几个比自己高的就行！就像这样：


xxxxxxxxxx
1
1
[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

该上第二节课的时候，大家记住了前面有几个比自己高的，却还是忘记了怎么排，老师见状让学生从高到低排好队，身高一样的，比自己高的越多，越往后面站，像这样：


xxxxxxxxxx
1
1
[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

每次让最高的学生出来找自己的位置，第一个高个子[7,0]自然站到了第一个位置：


xxxxxxxxxx
1
1
[[7,0]]

而第二个高个子[7,1]知道有一个人大于等于自己的身高，站在了第一个人身后：


xxxxxxxxxx
1
1
[[7,0],[7,1]]

第三个人[6,1]想了想，有一个人比自己高，那自己肯定站在第二位，于是就插队，现在也站到了第一个人身后：


xxxxxxxxxx
1
1
[[7,0],[6,1],[7,1]]

第四个人[5,0]想了想，没人比自己高，那自己肯定站在第一位，于是就插队，站到了队头：


xxxxxxxxxx
1
1
[[5,0],[7,0],[6,1],[7,1]]

第五个人[5,2]想了想，有两个人比自己高，于是就插队，站到了第二个人后面，也就是第三个位置：


xxxxxxxxxx
1
1
[[5,0],[7,0],[5,2],[6,1],[7,1]]

第六个人[4,4]看了看眼前的队伍，比自己高的人都在里面，他安心的数着前面有四个人比自己高，心安理得的站到了第四个人身后：


xxxxxxxxxx
1
1
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

其实这道题的大概思路就是这样，只有先让身高高的先进入队伍，后面身高低的才能根据前面高的来找自己的位置

C++:


xxxxxxxxxx
19
1
class Solution {
2
public:
3
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) 
4
    {
5
        sort(people.begin(),people.end(),[&](vector<int>&a,vector<int>&b)
6
        {
7
            return a[0]>b[0]||a[0]==b[0]&&a[1]<b[1];
8
        });//首先按照h从大到小排序，h相同时按照k从小到大排序
9
        for(int i=0;i<people.size();++i)
10
        {
11
            if(people[i][1]==i)
12
                continue;
13
            auto tmp=people[i];
14
            for(int j=i;j>tmp[1];--j)
15
                swap(people[j],people[j-1]);
16
        }
17
        return people;
18
    }
19
};

贪心17:用最少数量的箭引爆气球*

leetcode452

很经典的区间问题


xxxxxxxxxx
24
1
class Solution {
2
public:
3
    int findMinArrowShots(vector<vector<int>>& points) 
4
    {
5
        sort(points.begin(),points.end(),[&](vector<int>& a,vector<int>& b){
6
            return a[0]<b[0];
7
        });
8
        int i=0,ret=0;
9
        int len=points.size();
10
        while(i<len)
11
        {
12
            int left=points[i][0],right=points[i][1];
13
            int j=i+1;
14
            for(;j<len&&points[j][0]<=right;++j)
15
            {
16
                left=points[j][0];
17
                right=min(points[j][1],right);
18
            }
19
            ++ret;
20
            i=j;
21
        }
22
        return ret;
23
    }
24
};

贪心18:无重叠区间

leetcode435

首先按照右边界的坐标从小到大排序,如果右边界坐标相等,就按照左边界从大到小排序

然后从左到右遍历, 对于每个被遍历到的区间,都删除掉它后面所有与之相交的区间

被删除的区间不会再参与遍历

几种已经排好序的样例如下(带x的被删除掉)


xxxxxxxxxx
6
1
|--|
2
   |--|
3
|-----|            x
4
     |-----|       x
5
        |-------|
6
            |-----|x


xxxxxxxxxx
4
1
 |-|
2
|-----|        x
3
   |-----|
4
|-------------|x

C++:


xxxxxxxxxx
24
1
class Solution {
2
public:
3
    int eraseOverlapIntervals(vector<vector<int>>& intervals) 
4
    {
5
        int len=intervals.size();
6
        sort(intervals.begin(),intervals.end(),[&](vector<int>&a,vector<int>&b){
7
            return a[1]<b[1]||a[1]==b[1]&&a[0]>b[0];
8
        });
9
        int i=0,ret=0;
10
        while(i<len)
11
        {
12
            int j=i+1;
13
            for(;j<len;++j)
14
            {
15
                if(intervals[j][0]<intervals[i][1])
16
                    ++ret;
17
                else 
18
                    break;
19
            }
20
            i=j;
21
        }
22
        return ret;
23
    }
24
};

贪心19:划分字母区间

leetcode763

和上面两题相似,也是区间重叠问题

C++: 自己的糟糕代码


xxxxxxxxxx
38
1
class Solution {
2
public:
3
    vector<int> partitionLabels(string s) 
4
    {
5
        unordered_map<char,int>hash;//记录字母在数组vec中的下标
6
        vector<pair<int,int>>vec;//记录字母所有出现位置的左边界和右边界
7
        int len=0;//vec数组的长度
8
        for(int i=0;i<s.size();++i)
9
        {
10
            if(hash.find(s[i])==hash.end())
11
            {
12
                hash[s[i]]=len;
13
                ++len;
14
                vec.emplace_back(make_pair(i,i));
15
            }
16
            else
17
                vec[hash[s[i]]].second=i;
18
        }
19
        sort(vec.begin(),vec.end(),[&](pair<int,int>&a,pair<int,int>&b){
20
            return a.first<b.first;
21
        });
22
        int left=0,right=0;
23
        vector<int>ret;
24
        for(auto& p:vec)
25
        {
26
            if(p.first>right)
27
            {
28
                ret.emplace_back(right-left+1);
29
                left=p.first;
30
                right=p.second;
31
            }
32
            else
33
                right=max(right,p.second);
34
        }
35
        ret.emplace_back(right-left+1);
36
        return ret;
37
    }
38
};

大佬的优雅代码(搬运自https://leetcode.cn/problems/partition-labels/discussion/comments/31356):


xxxxxxxxxx
19
1
class Solution {
2
public:
3
    vector<int> partitionLabels(string S) {
4
        vector<int> result;
5
        unordered_map<char, int> map; //记录char c 和其最后出现位置的 map
6
        int start = 0, end = 0;
7
        for (int i = 0; i < S.size(); i ++) {
8
            map[S[i]] = i;
9
        }
10
        for (int i = 0; i < S.size(); i ++) {
11
            end = max(end, map[S[i]]);
12
            if (i == end) {
13
                result.push_back(end - start + 1);
14
                start = i + 1;
15
            }
16
        }
17
        return result;
18
    }
19
};

贪心20：合并区间

leetcode56


xxxxxxxxxx
26
1
class Solution {
2
public:
3
    vector<vector<int>> merge(vector<vector<int>>& intervals) 
4
    {
5
        sort(intervals.begin(),intervals.end(),[&](vector<int>&a,vector<int>&b){
6
            return a[0]<b[0];
7
        });
8
        int left=intervals[0][0],right=intervals[0][1];
9
        vector<vector<int>>ret;
10
        for(auto& vec:intervals)
11
        {
12
            if(vec[0]<=right)
13
            {
14
                right=max(right,vec[1]);
15
            }
16
            else
17
            {
18
                ret.emplace_back(vector<int>{left,right});
19
                left=vec[0];
20
                right=vec[1];
21
            }
22
        }
23
        ret.emplace_back(vector<int>{left,right});
24
        return ret;
25
    }
26
};

贪心22：单调递增的数字

leetcode738

方法1:从左到右遍历(作者的笨办法)

将n各个位填入数组(字符串也行),从左到右遍历:

当发现当前位数字比前一位数字小时,就开始修改字符串,修改完字符串就能返回结果

修改规则为:前一位数字减1,当前位数字及之后所有位的数字一律为9

例如6328,遍历到3时,将前1位减1得5,后面一律为9,得5999

考虑一种情况,n=332,遍历到下标2时发现数字比前一位小,将下标为1处的3改为2,后面置为9后,得329不符合题意,这说明还需要另外加一个循环从下标为1处向前遍历,如果当前位置数字比前一位小了,就把当前位置数字置为9,前一位数字减一,处理后数字变为299

C++: 0ms,59MB


xxxxxxxxxx
34
1
class Solution {
2
public:
3
    int monotoneIncreasingDigits(int n) 
4
    {
5
        string s=to_string(n);
6
        for(int i=1;i<s.size();++i)
7
        {
8
            if(s[i]<s[i-1])
9
            {
10
                --s[i-1];
11
                for(int j=i-1;j>=1;--j)
12
                {
13
                    if(s[j]<s[j-1])
14
                    {
15
                        s[j]='9';
16
                        --s[j-1];
17
                    }
18
                    else
19
                        break;
20
                }
21
                for(int j=i;j<s.size();++j)
22
                    s[j]='9';
23
                break;
24
            }
25
        }
26
        n=0;
27
        for(char& ch:s)
28
        {
29
            n*=10;
30
            n+=ch-'0';
31
        }
32
        return n;
33
    }
34
};

方法2:从右往左遍历(大佬的优雅方法)

C++: 4ms,5.9MB


xxxxxxxxxx
17
1
class Solution {
2
public:
3
    int monotoneIncreasingDigits(int n) 
4
    {
5
        string s=to_string(n);
6
        int flag;
7
        for(int i=s.size()-1;i>=1;--i)
8
            if(s[i-1]>s[i])
9
            {
10
                flag=i;
11
                --s[i-1];
12
            }
13
        for(int i=flag;i<s.size();++i)
14
            s[i]='9';
15
        return stoi(s);
16
    }
17
};

大佬虽然优雅,但耗时有点长

贪心23:监控二叉树

leetcode968

val: 1->安装监控 2->接受下方节点监控 3->接受上方节点监控


xxxxxxxxxx
28
1
class Solution {
2
public:
3
    int minCameraCover(TreeNode* root) 
4
    {
5
        int ret=0;//摄像头总数
6
        //采用后序遍历
7
        function<void(TreeNode*)>dfs=[&](TreeNode* cur)
8
        {
9
            if(cur->left!=nullptr)
10
                dfs(cur->left);
11
            if(cur->right!=nullptr)
12
                dfs(cur->right);
13
            if(cur->left!=nullptr&&cur->left->val==3||cur->right!=nullptr&&cur->right->val==3)//左孩子和右孩子中存在接受上方监控的节点
14
            {
15
                cur->val=1;//给当前节点安装监控
16
                ++ret;
17
            }
18
            else if(cur->left!=nullptr&&cur->left->val==1||cur->right!=nullptr&&cur->right->val==1)//左孩子和右孩子中存在装有监控的节点
19
                cur->val=2;//接受下方节点的监控
20
            else
21
                cur->val=3;//接受上方节点的监控
22
        };
23
        dfs(root);
24
        if(root->val==3)//可能出现root节点接受上方节点监控的情况,这时需要给root安装监控
25
            ++ret;
26
        return ret;
27
    }
28
};

图论

最小生成树:连接所有节点的最小费用

leetcode1584

本题为边稠密图,更适合普里姆算法

prim普里姆算法

从某一个顶点开始构建生成树,每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止

SysuGLM的解释:

Prim 算法是一种用于解决无向图最小生成树问题的贪心算法。它的基本思想是从一个顶点开始，不断地寻找与当前生成树距离最近的顶点，将其加入到生成树中，直到所有顶点都加入到生成树中为止。该算法是由捷克数学家 Vojtěch Jarník 于 1930 年发现的，并在 1957 年由美国计算机科学家 Robert C. Prim 重新发现，因此得名 Prim 算法。以下是 Prim 算法的基本步骤：
初始化一个空的最小生成树 T。
任选图中一个顶点 v，将其加入到 T 中。
在图中寻找距离 T 最近的顶点 u，将边 (u, v) 加入到 T 中。
重复步骤 3，直到所有顶点都加入到 T 中。
得到的 T 即为原图的最小生成树。
Prim 算法的时间复杂度取决于具体的实现方式。最简单的实现方式是用邻接矩阵表示图，其时间复杂度为 O(n^2)，其中 n 为图的顶点数。使用优先队列和邻接表可以进一步优化算法的性能，将时间复杂度降低到 O(nlogn)。

$O(V^2)$ , 适用于边稠密图


xxxxxxxxxx
38
1
class Solution {
2
public:
3
    int minCostConnectPoints(vector<vector<int>>& points)//prim算法
4
    {
5
        int n=points.size();//点的总数
6
        vector<int>isjoin(n);//是否已被连接
7
        vector<int>lowcost(n);//连入图的最小开销
8
        lowcost[0]=0;
9
        isjoin[0]=1;
10
        for(int i=1;i<n;++i)
11
            lowcost[i]=abs(points[i][0]-points[0][0])+abs(points[i][1]-points[0][1]);//初始化图，到0节点的最小距离
12
        int ret=0;
13
        for(int i=1;i<n;++i)
14
        {
15
            int cur_min=INT_MAX;
16
            int cur_idx;
17
            for(int j=1;j<n;++j)//寻找当前入图开销最小的节点
18
            {
19
                if(isjoin[j]==1)//排除已经入图的节点
20
                    continue;
21
                if(lowcost[j]<cur_min)
22
                {
23
                    cur_min=lowcost[j];
24
                    cur_idx=j;
25
                }
26
            }
27
            ret+=cur_min;
28
            isjoin[cur_idx]=1;
29
            for(int j=1;j<n;++j)//更新所有节点的入图距离
30
            {
31
                if(isjoin[j]==1)
32
                    continue;
33
                lowcost[j]=min(lowcost[j],abs(points[j][0]-points[cur_idx][0])+abs(points[j][1]-points[cur_idx][1]));
34
            }
35
        }
36
        return ret;
37
    }
38
};

Kruskal算法

SysuGLM的解释:

Kruskal 算法是一种贪心算法，用于求解连通网的最小生成树。具体步骤如下：
将所有的边按照权重从小到大排序。
初始化一个空集合，用于存放已选择的边。
按照排序后的顺序依次遍历每条边，检查当前边的两个顶点是否属于同一个连通分量（可以使用并查集数据结构进行快速判断）。如果不属于同一个连通分量，那么将这条边加入到已选择的边的集合中，并合并这两个顶点所在的连通分量；如果已经属于同一个连通分量，那么跳过这条边。
当已选择的边的数量等于顶点数减一时，算法结束。此时已选择的边构成了连通网的最小生成树。这种算法的时间复杂度为 O(ElogE)，其中 E 是边的数量。

该算法利用Quick Union版本的并查集, 有关并查集Quick Find和Quick Union版本的区别, 参考本文


xxxxxxxxxx
39
1
class Solution {
2
public:
3
    int minCostConnectPoints(vector<vector<int>>& points)//Kruskal算法
4
    {
5
        int n=points.size();
6
        vector<pair<int,int>>edge;
7
        edge.reserve(n*(n-1)/2);
8
        for(int i=0;i<n;++i)
9
            for(int j=i+1;j<n;++j)
10
                edge.emplace_back(make_pair(i,j));
11
        sort(edge.begin(),edge.end(),[&](pair<int,int>&a,pair<int,int>&b){
12
            return abs(points[a.first][0]-points[a.second][0])+abs(points[a.first][1]-points[a.second][1])<abs(points[b.first][0]-points[b.second][0])+abs(points[b.first][1]-points[b.second][1]);
13
        });
14
        vector<int>bing(n);
15
        for(int i=0;i<n;++i)
16
            bing[i]=i;
17
        function<int(int)>find=[&](int cur)
18
        {
19
            if(bing[cur]!=cur)
20
                return find(bing[cur]);
21
            else 
22
                return cur;
23
        };
24
        int ret=0;
25
        for(auto& p:edge)
26
        {
27
            int pf=find(p.first);
28
            int ps=find(p.second);
29
            if(pf==ps)
30
                continue;
31
            else
32
            {
33
                ret+=abs(points[p.first][0]-points[p.second][0])+abs(points[p.first][1]-points[p.second][1]);
34
                bing[pf]=ps;
35
            }
36
        }
37
        return ret;
38
    }
39
};

最后一个测试用例会超时😭

最短路径问题:

图出自王道考研数据结构

参考视频【王道计算机考研数据结构】

例题：

网络延迟时间leetcode743
【模板】单源最短路径（标准版）洛谷P4779
【模板】单源最短路径（弱化版）洛谷P3371

BFS算法比较基础，且只能处理不带权的图，这里就不介绍了

Dijkstra算法

当前算法适用于稠密图

求带权图的最短路径长度，局限是不能处理负权图

$V_0,V_1,...,V_{n-1}$ $V_0$ 到各个顶点的最短路径长度

初始化三个数组：

bool final[n]标记各个顶点是否已经找到最短路径，初始化为False
int dist[n] $+\infin$
int path[n] 各个顶点在路径上的前驱,初始化为-1


xxxxxxxxxx
51
1
#define inf 100000
2
class Solution {
3
public:
4
    int networkDelayTime(vector<vector<int>>& times, int n, int k) 
5
    {
6
        vector<vector<int>>arr(n+1);//邻接表
7
        for(int i=1;i<=n;++i)
8
            arr[i].resize(n+1,inf);//初始化邻接表为无穷大
9
        for(auto& time:times)
10
            arr[time[0]][time[1]]=time[2];
11
        //dijkstra算法
12
        vector<bool>final(n+1,false);//标记各个顶点是否已经找到最短路径，初始化为false
13
        vector<int>dist(n+1,inf);//到达各个顶点的最短路径长度
14
        vector<int>path(n+1,-1);//各个顶点在路径上的前驱,初始化为-1，在本题可有可无
15
        int cur=k;//cur是当前正在访问的节点
16
        final[cur]=true;
17
        int cnt=1;//cnt统计当前已找到最短路径的顶点数量
18
        dist[k]=0;
19
        for(;cnt<n;++cnt)
20
        {
21
            //计算并更新与当前节点直接相连，并且final值为false的全部节点的dist值
22
            for(int i=1;i<=n;++i)
23
            {
24
                if(final[i]==false&&arr[cur][i]<inf)
25
                {
26
                    dist[i]=min(dist[i],dist[cur]+arr[cur][i]);    
27
                }
28
            }
29
            //找到从当前节点出发，下一个最近的节点
30
            int tmp=inf,tmp_idx=-1;
31
            for(int i=1;i<=n;++i)
32
            {
33
                if(final[i]==false)
34
                {
35
                    if(dist[i]<tmp)
36
                    {
37
                        tmp=dist[i];
38
                        tmp_idx=i;
39
                    }
40
                }
41
            }
42
            if(tmp_idx==-1)
43
                return -1;//收不到信号的情况
44
            path[tmp_idx]=cur;
45
            cur=tmp_idx;//cur指向下一个要访问的节点
46
            //将下一个节点在final数组对应下标位置的值改为true
47
            final[cur]=true;
48
        }
49
        return *max_element(dist.begin()+1,dist.end());
50
    }
51
};

leetcode743通过,92ms,36.5MB

复杂度分析

$|V|$ $|V|$ $|V|$ 次

$O(|V|^2)$ $O(|V|^2)$ .(邻接矩阵占用的空间)

$|V|$ $O(|V|^3)$

Dijkstra算法优化:使用小根堆priority_queue

当前算法适用于稀疏图


xxxxxxxxxx
35
1
#define inf 10000
2
class Solution {
3
public:
4
    int networkDelayTime(vector<vector<int>>& times, int n, int k) 
5
    {
6
        using Pair=pair<int,int>;
7
        vector<vector<Pair>>vec(n+1);
8
        for(auto& time:times)
9
        {
10
            vec[time[0]].emplace_back(make_pair(time[1],time[2]));
11
        }
12
        priority_queue<Pair,vector<Pair>,greater<>>pq;
13
        vector<int>dist(n+1,inf);
14
        pq.emplace(0,k);//分别代表当前最小的dist值，及其对应下标
15
        dist[k]=0;
16
        while(!pq.empty())
17
        {
18
            auto cur=pq.top();//cur.first是当前处理节点的最小dist值,cur.second是当前处理节点的下标
19
            pq.pop();
20
            if(dist[cur.second]<cur.first)
21
                continue;
22
            auto& tmp=vec[cur.second];
23
            for(Pair& pa:tmp)//pa.first是下一个要处理的节点,pa.second是到该节点的距离
24
            {
25
                if(dist[pa.first]>cur.first+pa.second)
26
                {
27
                    dist[pa.first]=cur.first+pa.second;
28
                    pq.emplace(dist[pa.first],pa.first);
29
                }
30
            }
31
        }
32
        int ret=*max_element(dist.begin()+1,dist.end());
33
        return ret==inf?-1:ret;
34
    }
35
};

复杂度分析

$|V|$ $|E|$ $|E|$ $O(\log |E|)$ $|E|$ $O(|E|\log |E|)$

$O(|V|)$ $O(|E|)$ $O(|E|+|V|)$

Floyd算法

Floyd算法更加通用，可以解决带负权值的图，但前提是最短路径存在

如上图所示，要求A到C的最短路径，如果选择的路径是沿着箭头一直前进，每循环一圈路径长度减2，A到C的路径可以无穷小，不存在最短路径


xxxxxxxxxx
33
1
#define inf 100000
2
class Solution {
3
public:
4
    int networkDelayTime(vector<vector<int>>& times, int n, int k) //floyd算法
5
    {
6
        vector<vector<int>>arr(n+1,vector<int>(n+1,inf));//代表各顶点间的最短路径长度，初始化为邻接表
7
        for(auto& time:times)
8
            arr[time[0]][time[1]]=time[2];//不允许在其他节点中转，最短路径是
9
        vector<vector<int>>path(n+1,vector<int>(n+1,-1));//两个节点之间的中转点
10
        for(int i=1;i<=n;++i)//依次考虑以第i个节点为中转，更新
11
        {
12
            for(int j=1;j<=n;++j)//遍历所有可能的方向
13
            {
14
                for(int m=1;m<=n;++m)
15
                {
16
                    if(arr[j][m]>arr[j][i]+arr[i][m])
17
                    {
18
                        arr[j][m]=arr[j][i]+arr[i][m];
19
                        path[j][m]=i;
20
                    }
21
                }
22
            }
23
        }
24
        int ret=0;
25
        for(int i=1;i<=n;++i)
26
        {
27
            if(i==k)
28
                continue;
29
            ret=max(ret,arr[k][i]);
30
        }
31
        return ret==inf?-1:ret;
32
    }
33
};

leetcode743通过,160ms,37MB

复杂度分析

$O(|V|^3)$ $O(|V|^2)$

Bellman-ford算法

（引用自百度百科）

贝尔曼-福特算法与迪科斯彻算法贪心法 $|V|-1$
$|V|$ 是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。

CSDN Bellman-ford算法


xxxxxxxxxx
19
1
#define inf 10000000
2
class Solution {
3
public:
4
    int networkDelayTime(vector<vector<int>>& times, int n, int k) //Bellman-ford算法
5
    {
6
        vector<int>dist(n+1,inf);
7
        dist[k]=0;
8
        for(int i=0;i<n-1;++i)//循环n-1次，一定能松弛所有顶点，否则没有被松弛的收不到信号
9
        {
10
            for(auto& time:times)//遍历所有边
11
            {
12
                if(dist[time[0]]+time[2]<dist[time[1]])//松弛操作
13
                    dist[time[1]]=dist[time[0]]+time[2];
14
            }
15
        }
16
        int ret=*max_element(dist.begin()+1,dist.end());
17
        return ret==inf?-1:ret;
18
    }
19
};

leetcode743通过,152ms,35.7MB

$O(|V||E|)$ $|V|$ $|E|$ 是边数

SPFA算法

SPFA算法是对Bellman-ford算法的优化

shortest path faster algorithm

参考文献CSDN SPFA算法,画图详细解释了该算法,适合小白


xxxxxxxxxx
31
1
#define inf 100000000
2
class Solution {
3
public:
4
    int networkDelayTime(vector<vector<int>>& times, int n, int k) 
5
    {
6
        queue<int>que;
7
        vector<int>dist(n+1,inf);
8
        que.push(k);
9
        dist[k]=0;
10
        using Pair=pair<int,int>;
11
        vector<vector<Pair>>vec(n+1);//从i节点到vec[i].first有一条长度为vec[i].second的路径
12
        for(auto& time:times)
13
            vec[time[0]].emplace_back(time[1],time[2]);
14
        while(!que.empty())
15
        {
16
            int front=que.front();
17
            que.pop();
18
            auto& ve=vec[front];
19
            for(auto& p:ve)
20
            {
21
                if(dist[p.first]>dist[front]+p.second)
22
                {
23
                    dist[p.first]=dist[front]+p.second;
24
                    que.push(p.first);
25
                }
26
            }
27
        }
28
        int ret=*max_element(dist.begin()+1,dist.end());
29
        return ret==inf?-1:ret;
30
    }
31
};

leetcode743通过,84ms,39MB


xxxxxxxxxx
40
1
#include<iostream>
2
#include<vector>
3
#include<algorithm>
4
#include<queue>
5
using namespace std;
6
#define inf 0x7fffffff
7
int main()//SPFA算法
8
{
9
    int n,m,s;
10
    cin>>n>>m>>s;
11
    int u,v,w;
12
    using Pair=pair<int,int>;
13
    vector<vector<Pair>> g(n+1);//从i节点到g[i].first有一条长度为g[i].second的路径
14
    for(int i=0;i<m;++i)
15
    {
16
        cin>>u>>v>>w;
17
        g[u].emplace_back(v,w);
18
    }
19
    vector<int> dist(n+1,inf);
20
    dist[s]=0;
21
    queue<int> q;
22
    q.push(s);
23
    while(!q.empty())
24
    {
25
        int front=q.front();
26
        q.pop();
27
        for(auto& p:g[front])
28
        {
29
            if(dist[p.first]>dist[front]+p.second)
30
            {
31
                dist[p.first]=dist[front]+p.second;
32
                q.push(p.first);
33
            }
34
        }
35
    }
36
    for(int i=1;i<=n;++i)
37
        cout<<dist[i]<<" ";
38
    cout<<endl;
39
    return 0;
40
}

洛谷P3371 【模板】单源最短路径（弱化版）通过

$O(kE)$ ,k是每个点的平均进队次数(一般的，k是一个常数，在稀疏图中小于2)。
引用出处

拓扑排序

参考王道考研数据结构

AOV网(Activity On Vertex Network):用顶点表示活动的网

$<V_i,V_j>$ $V_i$ $V_j$ 进行

表示“番茄炒蛋工程”的AOV网

拓扑排序的一种结果:

拓扑排序的实现:

从AOV网中选择一个没有前驱(入度为0)的顶点并输出
在网中删除该顶点和所有以它为起点的有向边
重复步骤1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点(说明有回路)为止

出现回路的情况:

当前所有顶点的入度>0,说明原图存在回路

课程表

leetcode207

方法1：BFS


xxxxxxxxxx
32
1
class Solution {
2
public:
3
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
4
    {
5
        vector<vector<int>>vec(numCourses);//vec[i]存储完成课程i之后才能完成的课程
6
        vector<int>indegree(numCourses);//indegree[i]存储课程i在AOV网中的全部前驱节点
7
        for(auto& pre:prerequisites)
8
        {
9
            vec[pre[1]].emplace_back(pre[0]);
10
            ++indegree[pre[0]];
11
        }
12
        stack<int>sta;//当前所有入度为零的节点下标
13
        for(int i=0;i<numCourses;++i)
14
            if(indegree[i]==0)
15
                sta.push(i);//初始化栈
16
        int cnt=0;//统计当前已经遍历的节点数量
17
        while(!sta.empty())
18
        {
19
            int cur=sta.top();
20
            ++cnt;
21
            sta.pop();
22
            auto& ve=vec[cur];
23
            for(int& ve_:ve)
24
            {
25
                --indegree[ve_];
26
                if(indegree[ve_]==0)
27
                    sta.push(ve_);
28
            }
29
        }
30
        return cnt==numCourses;
31
    }
32
};

方法2：DFS

参考力扣官方题解


xxxxxxxxxx
44
1
class Solution {
2
public:
3
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
4
    {
5
        vector<vector<int>>vec(numCourses);//vec[i]存储完成课程i之后才可以完成的课程
6
        vector<bool>isvisited(numCourses,false);//记录节点i是否正在被访问
7
        vector<bool>isInStack(numCourses,false);//记录节点i是否已经入栈
8
        for(auto& pre:prerequisites)
9
        {
10
            vec[pre[1]].emplace_back(pre[0]);//初始化vec数组
11
        }
12
        int flag=0;//当flag==1时，说明正在被访问的结果遭到二次访问，说明图中有环，返回空数组
13
        function<void(int)>dfs=[&](int idx){
14
            if(flag)
15
                return;
16
            isvisited[idx]=true;
17
            auto& ve=vec[idx];//当前节点直接指向的节点
18
            for(int& ve_:ve)
19
            {
20
                if(!isvisited[ve_])//确保正在被访问的结果没有遭到二次访问
21
                {
22
                    if(!isInStack[ve_])
23
                        dfs(ve_);
24
                }
25
                else
26
                {
27
                    flag=1;
28
                    return;
29
                }
30
            }
31
            isvisited[idx]=false;
32
            isInStack[idx]=true;
33
        };
34
        for(int i=0;i<numCourses;++i)
35
            if(!isInStack[i])
36
            {
37
                dfs(i);
38
                if(flag)
39
                    return false;
40
            }
41
        return true;
42

43
    }
44
};

课程表II

leetcode210

方法1：BFS


xxxxxxxxxx
38
1
class Solution {
2
public:
3
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
4
    {
5
        vector<vector<int>>vec(numCourses);//vec[i]存储完成课程i之后才可以完成的课程
6
        vector<int>indegree(numCourses);//indegree[i]存储课程i节点的所有入度
7
        vector<int>ret;//返回的排序数组
8
        ret.reserve(numCourses);//预留空间
9
        stack<int>sta;
10
        for(auto& pre:prerequisites)
11
        {
12
            vec[pre[1]].emplace_back(pre[0]);//初始化vec数组
13
            ++indegree[pre[0]];//初始化indegree数组
14
        }
15
        for(int i=0;i<numCourses;++i)
16
            if(indegree[i]==0)
17
                sta.push(i);
18
        int cnt=0;//已经遍历过的节点数量
19
        while(!sta.empty())
20
        {
21
            ++cnt;
22
            int cur=sta.top();
23
            sta.pop();
24
            ret.emplace_back(cur);
25
            auto& ve=vec[cur];//完成当前课程之后才可以完成的课程
26
            for(int& ve_:ve)
27
            {
28
                --indegree[ve_];
29
                if(indegree[ve_]==0)
30
                    sta.push(ve_);
31
            }
32
        }
33
        if(cnt==numCourses)
34
            return ret;
35
        else
36
            return vector<int>();
37
    }
38
};

方法2：DFS


xxxxxxxxxx
52
1
class Solution {
2
public:
3
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
4
    {
5
        vector<vector<int>>vec(numCourses);//vec[i]存储完成课程i之后才可以完成的课程
6
        vector<bool>isvisited(numCourses,false);//记录节点i是否正在被访问
7
        vector<bool>isInStack(numCourses,false);//记录节点i是否已经入栈
8
        stack<int>sta;//存储逆拓扑排序序列
9
        for(auto& pre:prerequisites)
10
        {
11
            vec[pre[1]].emplace_back(pre[0]);//初始化vec数组
12
        }
13
        int flag=0;//当flag==1时，说明正在被访问的结果遭到二次访问，说明图中有环，返回空数组
14
        function<void(int)>dfs=[&](int idx){
15
            if(flag)
16
                return;
17
            isvisited[idx]=true;
18
            auto& ve=vec[idx];//当前节点直接指向的节点
19
            for(int& ve_:ve)
20
            {
21
                if(!isvisited[ve_])//确保正在被访问的结果没有遭到二次访问
22
                {
23
                    if(!isInStack[ve_])
24
                        dfs(ve_);
25
                }
26
                else
27
                {
28
                    flag=1;
29
                    return;
30
                }
31
            }
32
            sta.push(idx);
33
            isvisited[idx]=false;
34
            isInStack[idx]=true;
35
        };
36
        for(int i=0;i<numCourses;++i)
37
            if(!isInStack[i])
38
            {
39
                dfs(i);
40
                if(flag)
41
                    return vector<int>();
42
            }
43
        vector<int>ret;
44
        ret.reserve(numCourses);
45
        while(!sta.empty())
46
        {
47
            ret.emplace_back(sta.top());
48
            sta.pop();
49
        }
50
        return ret;
51
    }
52
};

图论1：统计点对的数目

leetcode1782

参考灵神的题解

利用算法：哈希表6.9:两数之和 II - 输入有序数组


xxxxxxxxxx
44
1
class Solution {
2
public:
3
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) 
4
    {
5
        vector<int>deg(n);
6
        unordered_map<int,int>cnt_e;
7
        for(auto& edge:edges)
8
        {
9
            int x=edge[0]-1,y=edge[1]-1;
10
            if(x>y)
11
                swap(x,y);
12
            ++deg[x];
13
            ++deg[y];
14
            ++cnt_e[x<<16|y];
15
        }
16
        vector<int>sorted_deg=deg;
17
        vector<int>ans(queries.size());
18
        sort(sorted_deg.begin(),sorted_deg.end());
19
        for(int j=0;j<queries.size();++j)
20
        {
21
            int q=queries[j];
22
            int left=0,right=n-1;
23
            while(left<right)
24
            {
25
                if(sorted_deg[left]+sorted_deg[right]>q)
26
                {
27
                    ans[j]+=right-left;
28
                    --right;
29
                }
30
                else
31
                    ++left;
32
            }
33
            for(auto& e:cnt_e)
34
            {
35
                int x=e.first>>16;
36
                int y=e.first&0xffff;
37
                int num=e.second;
38
                if(deg[x]+deg[y]>q&&deg[x]+deg[y]-num<=q)
39
                    --ans[j];
40
            }
41
        }
42
        return ans;
43
    }
44
};

代码随想录的刷题顺序:

动态规划3:爬楼梯

点击跳转

动态规划4:使用最小花费爬楼梯

点击跳转

动态规划6:不同路径

leetcode62

$C_{m+n-2}^{m-1}$


xxxxxxxxxx
13
1
typedef long long ll;
2
int uniquePaths(int m, int n)
3
{
4
    int a=m+n-2,b=m-1<n-1?m-1:n-1;
5
    if(b==0)
6
    return 1;
7
    ll ret=1;
8
    for(int i=0;i<b;++i)
9
    {
10
        ret=ret*(a-i)/(i+1);
11
    }
12
    return ret;
13
}

方法2:动态规划

python:


xxxxxxxxxx
12
1
class Solution:
2
    def uniquePaths(self, m: int, n: int) -> int:
3
        @cache
4
        def dfs(x,y):
5
            if x==1 and y==1:
6
                return 1
7
            if x==1:
8
                return dfs(x,y-1)
9
            if y==1:
10
                return dfs(x-1,y)
11
            return dfs(x-1,y)+dfs(x,y-1)
12
        return dfs(m,n)

动态规划7:不同路径II

leetcode63


xxxxxxxxxx
31
1
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize)
2
{
3
    if(obstacleGrid[0][0]==1)
4
        return 0;
5
    int row=obstacleGridSize;
6
    int col=obstacleGridColSize[0];
7
    int** arr=(int**)malloc(sizeof(int*)*(row+1));
8
    for(int i=0;i<=row;++i)
9
    {
10
        arr[i]=(int*)malloc(sizeof(int)*(col+1));
11
        memset(arr[i],0,(col+1)*sizeof(int));
12
    }
13
    arr[1][1]=1;
14
    for(int i=1;i<=row;++i)
15
    {
16
        int j=1;
17
        if(i==1)
18
            j=2;
19
        for(;j<=col;++j)
20
        {
21
            if(obstacleGrid[i-1][j-1]==1)
22
                continue;
23
            arr[i][j]=arr[i-1][j]+arr[i][j-1];
24
        }
25
    }
26
    int ret=arr[row][col];
27
    for(int i=0;i<=row;++i)
28
        free(arr[i]);
29
    free(arr);
30
    return ret;
31
}

python:


xxxxxxxxxx
14
1
class Solution:
2
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
3
        @cache
4
        def dfs(x,y):
5
            if obstacleGrid[x-1][y-1]==1:
6
                return 0
7
            if x==1 and y==1:
8
                return 1
9
            if x==1:
10
                return dfs(x,y-1)
11
            if y==1:
12
                return dfs(x-1,y)
13
            return dfs(x-1,y)+dfs(x,y-1)
14
        return dfs(len(obstacleGrid),len(obstacleGrid[0]))

动态规划8:整数拆分

点击跳转

动态规划9:不同的二叉搜索树

点击跳转

0-1背包系列 13~17

动态规划13:分割等和子集

点击跳转

动态规划14：最后一块石头的重量II

点击跳转

动态规划16：目标和

点击跳转

动态规划17：一和零

点击跳转

完全背包系列 19~26

动态规划19：零钱兑换II

点击跳转

动态规划21：组合总和IV

点击跳转

动态规划23：零钱兑换

点击跳转

动态规划24：完全平方数

点击跳转

动态规划26：单词拆分

leetcode139

方法1：BFS(广度优先搜索)+记忆化搜索


xxxxxxxxxx
43
1
class Solution {
2
public:
3
    bool wordBreak(string s, vector<string>& wordDict) 
4
    {
5
        unordered_map<int,int>hash;
6
        queue<int> que;
7
        int wlen=wordDict.size();
8
        int slen=s.size();
9
        que.push(0);
10
        while(!que.empty())
11
        {
12
            int cur=que.front();
13
            if(cur==slen)
14
                return true;
15
            que.pop();
16
            vector<int>wor(wlen,1);
17
            int findnum=wlen;
18
            for(int i=0;cur+i<=slen&&findnum>0;++i)
19
            {
20
                for(int j=0;j<wlen;++j)
21
                {
22
                    if(wor[j]==0)
23
                        continue;
24
                    if(i>=wordDict[j].size())
25
                    {
26
                        if(hash[cur+wordDict[j].size()]==0)
27
                            que.push(cur+wordDict[j].size());
28
                        hash[cur+wordDict[j].size()]=1;
29
                        --findnum;
30
                        wor[j]=0;
31
                        continue;
32
                    }
33
                    if(s[cur+i]!=wordDict[j][i])
34
                    {
35
                        --findnum;
36
                        wor[j]=0;
37
                    }
38
                }
39
            }
40
        }
41
        return false;
42
    }
43
};

方法2：完全背包

(出自代码随想录)

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词，说明就是一个完全背包！


xxxxxxxxxx
20
1
class Solution:
2
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
3
        @cache
4
        def dp(i,c):
5
            if c==-1:
6
                return 1
7
            if i<0:
8
                return 0
9
            flag=1
10
            le=len(wordDict[i])
11
            if c<le-1:
12
                return dp(i-1,c)
13
            for idx,ch in enumerate(wordDict[i]):
14
                if s[c-le+1+idx]!=ch:
15
                    flag=0
16
                    break
17
            if flag==1:
18
                return dp(i-1,c)+dp(len(wordDict)-1,c-le)
19
            return dp(i-1,c)
20
        return dp(len(wordDict)-1,len(s)-1)!=0

打家劫舍问题29-31

动态规划29：打家劫舍

点击跳转

动态规划30：打家劫舍II

点击跳转

动态规划31：打家劫舍III

leetcode337

每个节点都有偷和不偷两种选择，用pair对组存储两种情况下的最大收益

如果偷了当前节点，则左右节点都不能偷，只有一种情况

如果不偷当前节点，有四种情况：偷左右节点、偷左不偷右、偷右不偷左、左右都不偷


xxxxxxxxxx
21
1
class Solution {
2
public:
3
    int rob(TreeNode* root) 
4
    {
5
        int ret=0;
6
        //pair中存储的分别是偷和不偷的最大收益
7
        function<pair<int,int>(TreeNode*)>dfs=[&](TreeNode* cur)
8
        {
9
            if(cur==nullptr)
10
                return make_pair(0,0);
11
            auto pl=dfs(cur->left);
12
            auto pr=dfs(cur->right);
13
            int steal=cur->val+pl.second+pr.second;
14
            int noSteal=max(pl.first+pr.second,max(pl.second+pr.first,max(pl.first+pr.first,pl.second+pr.second)));
15
            ret=max(ret,max(steal,noSteal));
16
            return make_pair(steal,noSteal);
17
        };
18
        dfs(root);
19
        return ret;
20
    }
21
};

股票问题32-38

动态规划32.买卖股票的最佳时机

leetcode121

方法1：贪心

用双指针实现，左指针取最小值，右指针取最大值，差值就是最大利润


xxxxxxxxxx
21
1
#define fmax(x,y) ((x)>(y)?(x):(y))
2
int maxProfit(int* prices, int pricesSize)
3
{
4
    int min=0,max=0;
5
    int ret=0;
6
    for(int i=1;i<pricesSize;++i)
7
    {
8
        if(prices[i]<prices[min])
9
        {
10
            ret=fmax(ret,prices[max]-prices[min]);
11
            min=i;
12
            max=i;
13
        }
14
        else if(prices[i]>prices[max])
15
        {
16
            max=i;
17
            ret=fmax(ret,prices[max]-prices[min]);
18
        }
19
    }
20
    return ret;
21
}

方法2：动态规划

维护两个变量，分别是have今天结束后持有股票的最大利润，notHave今天结束后不持有股票的最大利润

python:


xxxxxxxxxx
10
1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        have=-prices[0]  # 当前持有股票的最大利润
4
        notHave=0  # 当前不持有股票的最大利润
5
        for i in range(1,len(prices)):
6
            tp1=max(have,-prices[i])
7
            tp2=max(notHave,have+prices[i])
8
            have=tp1
9
            notHave=tp2
10
        return notHave

动态规划34.买卖股票的最佳时机II

详见贪心章节

总结一下32题和34题的动态规划区别

32题的特点是只能买一次：

今天持有股票的最大利润=max{昨天持有股票的最大利润(继承了昨天的情况)，今天买股票后的利润(-今天的股价)}
今天不持有股票的最大利润=max{昨天不持有股票的最大利润(继承了昨天的情况)，今天卖股票后的利润(卖掉昨天持有的)}

34题的特点是无限次购买:

今天持有股票的最大利润=max{昨天持有股票的最大利润(继承了昨天的情况)，在昨天不持有股票的基础上今天买股票后的利润(昨天不持有股票的利润-今天的股价)}
今天不持有股票的最大利润=max{昨天不持有股票的最大利润(继承了昨天的情况)，今天卖股票后的利润(卖掉昨天持有的)}

除了标黄的部分，两题的递推公式都是一样的

对比代码：

32题：

tp1=max(have,-prices[i])

tp2=max(notHave,have+prices[i])

34题：

tp1=max(have,notHave-prices[i])

tp2=max(notHave,have+prices[i])

动态规划35.买卖股票的最佳时机III

leetcode123

本题是下一题的削减版，对应下一题的k=2情况

动态规划：

注意，如果你用的是C++，-inf不能简单地用INT_MIN代替，因为动态规划过程中可能会涉及到对INT_MAX减去一个正数的操作

		3	3	5	0	0	3	1	4
0	第一次持有	-3	-3	-3	0	0	0	0	0
1	第一次卖出	-inf	0	2	2	2	3	3	4
2	第二次持有	-inf	-inf	-5	2	2	2	2	2
3	第二次卖出	-inf	-inf	-inf	-5	2	5	5	6


xxxxxxxxxx
5
1
dp[i][0]=max{dp[i-1][0],-prices[i]}
2
dp[i][1]=max{dp[i-1][1],dp[i-1][0]+prices[i]}
3
dp[i][2]=max{dp[i-1][2],dp[i-1][1]-prices[i]}
4
dp[i][3]=max{dp[i-1][3],dp[i-1][2]+prices[i]}
5
......

python:


xxxxxxxxxx
24
1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        k=2  # 最多完成k笔交易
4
        n=len(prices)
5
        # 构造数组
6
        dp=[[0]]*n
7
        for i in range(n):
8
            dp[i]=[0]*(2*k)
9
        # 数组初始化第一行
10
        dp[0][0]=-prices[0]
11
        for i in range(1,2*k):
12
            dp[0][i]=-inf
13
        # 开始递推
14
        for i in range(1,n):
15
            dp[i][0]=max(dp[i-1][0],-prices[i]) #第1列的递推
16
            for j in range(1,2*k):
17
                if j%2==0:  # 偶数列，表示第j//2次持有
18
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])
19
                else:  # 奇数列，表示第j//2+1次卖出
20
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i])
21
        ret=0
22
        for i in range(2*k):
23
            ret=max(ret,dp[n-1][i])
24
        return ret

C++: 实现上有些区别，比如将每次持有和卖出的两种情况压缩到对组内


xxxxxxxxxx
37
1
class Solution {
2
public:
3
    int maxProfit(vector<int>& prices) 
4
    {
5
        using ll=long long;
6
        int k=2;
7
        if(prices.size()==0)
8
            return 0;
9
        vector<vector<pair<ll,ll>>> dfs(prices.size());
10
        for(auto&vec:dfs)
11
            vec.resize(k+1);
12
        for(auto& pa:dfs[0])
13
        {
14
            pa.first=INT_MIN;
15
            pa.second=INT_MIN;
16
        }
17
        dfs[0][0].first=0;
18
        dfs[0][1].second=-prices[0];
19
        for(int i=1;i<prices.size();++i)
20
        {
21
            for(int j=0;j<=k;++j)
22
            {
23
                dfs[i][j].first=max(dfs[i-1][j].first,dfs[i-1][j].second+prices[i]);
24
                if(j==0)
25
                    dfs[i][j].second=dfs[i-1][j].second;
26
                else
27
                    dfs[i][j].second=max(dfs[i-1][j].second,dfs[i-1][j-1].first-prices[i]);
28
            }
29
        }
30
        ll ret=0;
31
        for(int i=0;i<=k;++i)
32
        {
33
            ret=max(ret,dfs[prices.size()-1][i].first);
34
        }
35
        return ret;
36
    }
37
};

动态规划36：买卖股票的最佳时机IV

leetcode188

解析见上一题

python:


xxxxxxxxxx
23
1
class Solution:
2
    def maxProfit(self, k: int, prices: List[int]) -> int:
3
        n=len(prices)
4
        # 构造数组
5
        dp=[[0]]*n
6
        for i in range(n):
7
            dp[i]=[0]*(2*k)
8
        # 数组初始化第一行
9
        dp[0][0]=-prices[0]
10
        for i in range(1,2*k):
11
            dp[0][i]=-inf
12
        # 开始递推
13
        for i in range(1,n):
14
            dp[i][0]=max(dp[i-1][0],-prices[i]) #第1列的递推
15
            for j in range(1,2*k):
16
                if j%2==0:  # 偶数列，表示第j//2次持有
17
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])
18
                else:  # 奇数列，表示第j//2+1次卖出
19
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i])
20
        ret=0
21
        for i in range(2*k):
22
            ret=max(ret,dp[n-1][i])
23
        return ret

C++:


xxxxxxxxxx
36
1
using ll=long long;
2
class Solution {
3
public:
4
    int maxProfit(int k, vector<int>& prices) 
5
    {
6
        if(prices.size()==0||k==0)
7
            return 0;
8
        vector<vector<pair<ll,ll>>> dfs(prices.size());
9
        for(auto&vec:dfs)
10
            vec.resize(k+1);
11
        for(auto& pa:dfs[0])
12
        {
13
            pa.first=INT_MIN;
14
            pa.second=INT_MIN;
15
        }
16
        dfs[0][0].first=0;
17
        dfs[0][1].second=-prices[0];
18
        for(int i=1;i<prices.size();++i)
19
        {
20
            for(int j=0;j<=k;++j)
21
            {
22
                dfs[i][j].first=max(dfs[i-1][j].first,dfs[i-1][j].second+prices[i]);
23
                if(j==0)
24
                    dfs[i][j].second=dfs[i-1][j].second;
25
                else
26
                    dfs[i][j].second=max(dfs[i-1][j].second,dfs[i-1][j-1].first-prices[i]);
27
            }
28
        }
29
        ll ret=0;
30
        for(int i=0;i<=k;++i)
31
        {
32
            ret=max(ret,dfs[prices.size()-1][i].first);
33
        }
34
        return ret;
35
    }
36
};

动态规划37：买卖股票的最佳时机含冷冻期

leetcode309

方法1：划分出三种状态

		1	2	3	0	2
0	持有股票	-1	-1	-1	1	1
1	保持卖出股票	0	0	1	2	2
2	卖出股票	-inf	1	2	-1	3


xxxxxxxxxx
3
1
dp[i][0]=max{dp[i-1][0],dp[i-1][1]-prices[i]}
2
dp[i][1]=max{dp[i-1][1],dp[i-1][2]}
3
dp[i][2]=dp[i-1][0]+prices[i]

python:


xxxxxxxxxx
15
1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        n=len(prices)
4
        # 构造dp数组
5
        dp=[[0]*3 for _ in range(n)]
6
        # 初始化第一行
7
        dp[0][0]=-prices[0]
8
        dp[0][1]=0
9
        dp[0][2]=-inf
10
        for i in range(1,n):
11
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i])
12
            dp[i][1]=max(dp[i-1][1],dp[i-1][2])
13
            dp[i][2]=dp[i-1][0]+prices[i]
14
        ret=max(dp[n-1][1],dp[n-1][2])
15
        return 0 if ret<0 else ret

方法2：两种状态(带下划线的初始化要特殊考虑)

		1	2	3	0	2
0	不持有股票	0	1	2	2	3
1	持有股票	-1	-1	-1	1	1


xxxxxxxxxx
2
1
dp[i][0]=max{dp[i-1][0],dp[i-1][1]+prices[i]}
2
dp[i][1]=max{dp[i-1][1],dp[i-2][0]-prices[i]}

python:记忆化递归


xxxxxxxxxx
10
1
class Solution:
2
    def maxProfit(self, prices: List[int]) -> int:
3
        @cache
4
        def dfs(i,hold):
5
            if i<0:
6
                return -inf if hold else 0
7
            if hold:
8
                return max(dfs(i-1,True),dfs(i-2,False)-prices[i])
9
            return max(dfs(i-1,False),dfs(i-1,True)+prices[i])
10
        return dfs(len(prices)-1,False)

C++:


xxxxxxxxxx
20
1
class Solution {
2
public:
3
    int maxProfit(vector<int>& prices) 
4
    {
5
        int len=prices.size();
6
        if(len<=1)
7
            return 0;
8
        vector<pair<int,int>>dfs(len);
9
        dfs[0].first=0;
10
        dfs[0].second=-prices[0];
11
        dfs[1].second=max(-prices[1],dfs[0].second);
12
        dfs[1].first=max(0,dfs[0].second+prices[1]);
13
        for(int i=2;i<len;++i)
14
        {
15
            dfs[i].first=max(dfs[i-1].first,dfs[i-1].second+prices[i]);
16
            dfs[i].second=max(dfs[i-1].second,dfs[i-2].first-prices[i]);
17
        }
18
        return dfs[len-1].first;
19
    }
20
};

动态规划38：买卖股票的最佳时机含手续费

leetcode714

fee=2

		1	3	2	8	4	9
0	不持有股票	0	0	0	5	5	8
1	持有股票	-3	-3	-3	-3	-1	-1


xxxxxxxxxx
2
1
dp[i][0]=max{dp[i-1][0],dp[i-1][1]+prices[i]}
2
dp[i][1]=max{dp[i-1][1],dp[i-1][0]-prices[i]-fee}

python:递归


xxxxxxxxxx
10
1
class Solution:
2
    def maxProfit(self, prices: List[int], fee: int) -> int:
3
        @cache
4
        def dfs(i,hold):
5
            if i<0:
6
                return -inf if hold else 0
7
            if hold:
8
                return max(dfs(i-1,True),dfs(i-1,False)-prices[i]-fee)
9
            return max(dfs(i-1,False),dfs(i-1,True)+prices[i])
10
        return dfs(len(prices)-1,False)

C++:递推


xxxxxxxxxx
16
1
class Solution {
2
public:
3
    int maxProfit(vector<int>& prices, int fee) 
4
    {
5
        int len=prices.size();
6
        vector<pair<int,int>> dfs(len);
7
        dfs[0].first=0;
8
        dfs[0].second=-prices[0]-fee;
9
        for(int i=1;i<len;++i)
10
        {
11
            dfs[i].first=max(dfs[i-1].first,dfs[i-1].second+prices[i]);
12
            dfs[i].second=max(dfs[i-1].second,dfs[i-1].first-fee-prices[i]);
13
        }
14
        return dfs[len-1].first;
15
    }
16
};

子序列问题

动态规划41：最长递增子序列

leetcode300

n为nums数组长度

方法1：动态规划

dp[i]表示以i为结尾的最长子序列

$O(n^2)$


xxxxxxxxxx
22
1
class Solution {
2
public:
3
    int lengthOfLIS(vector<int>& nums) 
4
    {
5
        int len=nums.size();
6
        vector<int> dp(len,1);
7
        int ret=1;
8
        for(int i=1;i<len;++i)
9
        {
10
            int tmp=0;
11
            for(int j=0;j<i;++j)
12
            {
13
                if(nums[j]<nums[i])
14
                    tmp=max(tmp,dp[j]);
15
            }
16
            if(tmp>0)
17
                dp[i]=tmp+1;
18
            ret=max(ret,dp[i]);
19
        }
20
        return ret;
21
    }
22
};

方法2：贪心+二分查找

g[i]为长度为i+1的子序列末尾元素的最小值

$O(n\log(n))$

g数组性质：1、严格递增 2、只更新一个位置，更新的位置是第一个>=nums[i]的数的下标


xxxxxxxxxx
17
1
class Solution {
2
public:
3
    int lengthOfLIS(vector<int>& nums) 
4
    {
5
        int len=nums.size();
6
        vector<int>greed={nums[0]};
7
        for(int i=1;i<len;++i)
8
        {
9
            auto it=lower_bound(greed.begin(),greed.end(),nums[i]);
10
            if(it==greed.end())
11
                greed.emplace_back(nums[i]);
12
            else
13
                *it=nums[i];
14
        }
15
        return greed.size();
16
    }
17
};

动态规划42：最长连续递增序列

leetcode674

简单题，大佬们可以跳过


xxxxxxxxxx
12
1
class Solution:
2
    def findLengthOfLCIS(self, nums: List[int]) -> int:
3
        n=len(nums)
4
        ret=1
5
        tmp=1
6
        for i in range(1,n):
7
            if nums[i]>nums[i-1]:
8
                tmp+=1
9
                ret=max(ret,tmp)
10
            else:
11
                tmp=1
12
        return ret

动态规划43：最长公共子序列

leetcode718


xxxxxxxxxx
12
1
class Solution:
2
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
3
        n1=len(nums1)
4
        n2=len(nums2)
5
        dp=[[0]*(n2+1) for _ in range(n1+1)]
6
        ret=0
7
        for i in range(1,n1+1):
8
            for j in range(1,n2+1):
9
                if nums1[i-1]==nums2[j-1]:
10
                    dp[i][j]=dp[i-1][j-1]+1
11
                    ret=max(ret,dp[i][j])
12
        return ret

动态规划44：最长公共子序列

点击跳转

动态规划45：不相交的线

leetcode1035

	5	2	1	5	2
2	0	1	1	1	1
5	1	1	1	2	2
1	1	1	2	2	2
2	1	2	2	2	3
5	1	2	2	3	3

\begin{matrix} d p [i] [j] = {\begin{cases} d p [i - 1] [j - 1] + 1, n u m s 1 [i] = n u m s 2 [j] \\ m a x {d p [i - 1] [j], d p [i] [j - 1]}, n u m s 1 [i] \neq n u m s 2 [j] \end{cases} \end{matrix}

python:


xxxxxxxxxx
10
1
class Solution:
2
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
3
        @cache
4
        def dp(i,j):
5
            if i<0 or j<0:
6
                return 0
7
            if nums1[i]==nums2[j]:
8
                return dp(i-1,j-1)+1
9
            return max(dp(i-1,j),dp(i,j-1))
10
        return dp(len(nums1)-1,len(nums2)-1)

动态规划46：最大子序和

leetcode53

代码随想录：

dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。
确定递推公式
dp[i]只有两个方向可以推出来：
dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
nums[i]，即：从头开始计算当前连续子序列和
一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

C++


xxxxxxxxxx
13
1
class Solution {
2
public:
3
    int maxSubArray(vector<int>& nums) 
4
    {
5
        int ret=nums[0],add=nums[0];
6
        for(int i=1;i<nums.size();++i)
7
        {
8
            add=max(add+nums[i],nums[i]);
9
            ret=max(ret,add);
10
        }
11
        return ret;
12
    }
13
};

python


xxxxxxxxxx
8
1
class Solution:
2
    def maxSubArray(self, nums: List[int]) -> int:
3
        add=0
4
        ret=-100000
5
        for num in nums:
6
            add=max(add+num,num)
7
            ret=max(ret,add)
8
        return ret

动态规划47：判断子序列

leetcode392

本题和45：不相交的线很像


xxxxxxxxxx
10
1
class Solution:
2
    def isSubsequence(self, s: str, t: str) -> bool:
3
        @cache
4
        def dp(i,j):
5
            if i<0 or j<0:
6
                return 0
7
            if s[i]==t[j]:
8
                return dp(i-1,j-1)+1
9
            return max(dp(i-1,j),dp(i,j-1))
10
        return dp(len(s)-1,len(t)-1)==len(s)

动态规划48：不同的子序列

leetcode115

dp(i,j)表示字符串t的前i+1个字母（t[0:i+1]）在字符串s的前j+1个字母（s[0:j+1]）的子序列中出现的次数

dp(i,j)	s[j]	b	a	b	g	b	a	g
t[i]	1	1	1	1	1	1	1	1
b	0	1	1	2	2	3	3	3
a	0	0	1	1	1	1	4	4
g	0	0	0	0	1	1	1	5

\begin{matrix} d p (i, j) = {\begin{cases} d p (i, j - 1) + d p (i - 1, j - 1), t [i] = s [j] \\ d p (i, j - 1), t [i] \neq s [j] \end{cases} \end{matrix}

解析：

当t[i]!=s[j]时，当前的两个字符不匹配，dp(i,j)=dp(i,j-1)，t[0:i+1]和s[0:j+1]的匹配问题可以转化为t[0:i+1]和s[0:j]的匹配问题。

举个例子，s=“bab”和t=“ba”不同子序列数，等价于s=“ba”和t=“ba”的不同子序列数，因为前者两个串末尾不同，可以看作s1新增的末尾字母b对不同子序列数不构成影响

当t[i]==s[j]时，当前的两个字符匹配，dp(i,j)=dp(i,j-1)+dp(i-1,j-1)。

举个例子，s=“babgba”和t=“ba”的不同子序列数，等于s=“babgb”和g=“ba”的子序列数，加上s=“babgb”，t=“b”的子序列数。

s=“babgb”，t=“b”的子序列数，包括了在字母a加入字符串t和s之前，s和t的子序列匹配数。加入a实际上是在之前已经匹配的子序列的基础上，延长了那些子序列。可以看出这里字母b匹配了三次，给两个串同时加上a，就变成了ba匹配了三次
s=“babgb”和g=“ba”的子序列数，是考虑在字母加入字符串s之前，s和t的子序列匹配数。可以看出s和t已经匹配了一对ba，再给s加入a对之前的匹配不构成影响。

python:(记忆化递归)


xxxxxxxxxx
12
1
class Solution:
2
    def numDistinct(self, s: str, t: str) -> int:  # 记忆化递归dp
3
        @cache
4
        def dp(i,j):
5
            if i<0:
6
                return 1
7
            if j<0:
8
                return 0
9
            if t[i]==s[j]:
10
                return dp(i,j-1)+dp(i-1,j-1)
11
            return dp(i,j-1)
12
        return dp(len(t)-1,len(s)-1)

C++


xxxxxxxxxx
21
1
class Solution {
2
public:
3
    int numDistinct(string s, string t) //递推版dp
4
    {
5
        using ll=unsigned long long;
6
        int slen=s.size(),tlen=t.size();
7
        //初始化二维数组
8
        vector<vector<ll>>dp(tlen+1);
9
        dp[0].resize(slen+1,1);
10
        for(int i=1;i<=tlen;++i)
11
            dp[i].resize(slen+1);
12
        //递推
13
        for(int i=1;i<=tlen;++i)
14
            for(int j=1;j<=slen;++j)
15
                if(t[i-1]==s[j-1])
16
                    dp[i][j]=dp[i][j-1]+dp[i-1][j-1];
17
                else
18
                    dp[i][j]=dp[i][j-1];
19
        return dp[tlen][slen];
20
    }
21
};

Javascript


xxxxxxxxxx
24
1
/**
2
 * @param {string} s
3
 * @param {string} t
4
 * @return {number}
5
 */
6
var numDistinct = function(s, t) //递推版dp
7
{
8
    let dp=new Array();
9
    for(let i=0;i<=t.length;++i)
10
        dp[i]=new Array();
11
    for(let i=0;i<=s.length;++i)
12
        dp[0][i]=1;
13
    for(let i=1;i<=t.length;++i)
14
        dp[i][0]=0;
15
    for(let i=1;i<=t.length;++i)
16
        for(let j=1;j<=s.length;++j)
17
        {
18
            if(t[i-1]==s[j-1])
19
                dp[i][j]=dp[i][j-1]+dp[i-1][j-1];
20
            else
21
                dp[i][j]=dp[i][j-1];
22
        }
23
    return dp[t.length][s.length];
24
};

动态规划49：两个字符串的删除操作

leetcode583

这题本质上和动态规划43：最长公共子序列相同

python:


xxxxxxxxxx
10
1
class Solution:
2
    def minDistance(self, word1: str, word2: str) -> int:
3
        @cache
4
        def dp(i,j):
5
            if i<0 or j<0:
6
                return 0
7
            if word1[i]==word2[j]:
8
                return dp(i-1,j-1)+1
9
            return max(dp(i-1,j),dp(i,j-1))
10
        return len(word1)+len(word2)-2*dp(len(word1)-1,len(word2)-1)


xxxxxxxxxx
35
1
#define max(x,y) (x)>(y)?(x):(y)
2
int longestCommonSubsequence(char * text1, char * text2)
3
{
4
    char s1[1005]=" ",s2[1005]=" ";
5
    strcat(s1,text1);
6
    strcat(s2,text2);
7
    int l1=strlen(text1);
8
    int l2=strlen(text2);
9
    int** mat=(int**)malloc((l1+1)*sizeof(int*));
10
    for(int i=0;i<=l1;++i)
11
        mat[i]=(int*)malloc((l2+1)*sizeof(int));
12
    for(int i=0;i<=l1;++i)
13
        mat[i][0]=0;
14
    for(int i=0;i<=l2;++i)
15
        mat[0][i]=0;
16
    for(int i=1;i<=l1;++i)
17
    {
18
        for(int j=1;j<=l2;++j)
19
        {
20
            if(s1[i]==s2[j])
21
                mat[i][j]=mat[i-1][j-1]+1;
22
            else
23
                mat[i][j]=max(mat[i-1][j],mat[i][j-1]);
24
        }
25
    }
26
    int ret=mat[l1][l2];
27
    for(int i=0;i<=l1;++i)
28
        free(mat[i]);
29
    free(mat);
30
    return ret;
31
}
32
int minDistance(char * word1, char * word2)
33
{
34
    return strlen(word1)+strlen(word2)-2*longestCommonSubsequence(word1,word2);
35
}

动态规划50：编辑距离

点击跳转

动态规划52：回文子串

leetcode647

$O(n^2)$


xxxxxxxxxx
35
1
class Solution {
2
public:
3
    int countSubstrings(string s) 
4
    {
5
        int n=s.size();
6
        int ret=n;
7
        for(int i=1;i<n-1;++i)
8
        {
9
            int left=i-1,right=i+1;
10
            while(left>=0&&right<n)
11
            {
12
                if(s[left]==s[right])
13
                    ++ret;
14
                else
15
                    break;
16
                --left;
17
                ++right;
18
            }
19
        }
20
        for(int i=0;i<n-1;++i)
21
        {
22
            int left=i,right=i+1;
23
            while(left>=0&&right<n)
24
            {
25
                if(s[left]==s[right])
26
                    ++ret;
27
                else
28
                    break;
29
                --left;
30
                ++right;
31
            }
32
        }
33
        return ret;
34
    }
35
};

$O(n^2)$ ，就懒得写了

动态规划53：最长回文子序列

leetcode516

dp(i,j)表示在区间[i,j]内最长回文子序列的长度


xxxxxxxxxx
12
1
class Solution:
2
    def longestPalindromeSubseq(self, s: str) -> int:
3
        @cache
4
        def dp(i,j):
5
            if i==j:
6
                return 1
7
            if i>j:
8
                return 0
9
            if s[i]==s[j]:
10
                return dp(i+1,j-1)+2
11
            return max(dp(i,j-1),dp(i+1,j))
12
        return dp(0,len(s)-1)

动态规划54：切披萨的方案数

leetcode1444

考察二维差分和三维动态规划

此题定义了pi数组，pi[i][j]意义为pizza数组中左上角(i,j)到右下角(row-1,col-1)矩形区域内苹果总数

dp(i,j,c)的意义为左上角(i,j)到右下角(row-1,col-1)矩形区域切c刀的方案总数


xxxxxxxxxx
36
1
class Solution:
2
    def ways(self, pizza: List[str], k: int) -> int:
3
        mod=10**9+7
4
        row=len(pizza)
5
        col=len(pizza[0])
6
        pi=[[0]*col for _ in range(row)]
7
        if pizza[row-1][col-1]=="A":
8
            pi[row-1][col-1]=1
9
        for i in range(row-2,-1,-1):
10
            pi[i][col-1]=pi[i+1][col-1]
11
            if pizza[i][col-1]=="A":
12
                pi[i][col-1]+=1
13
        for i in range(col-2,-1,-1):
14
            pi[row-1][i]=pi[row-1][i+1]
15
            if pizza[row-1][i]=="A":
16
                pi[row-1][i]+=1
17
        for i in range(row-2,-1,-1):
18
            for j in range(col-2,-1,-1):
19
                pi[i][j]=pi[i+1][j]+pi[i][j+1]-pi[i+1][j+1]
20
                if pizza[i][j]=="A":
21
                    pi[i][j]+=1
22
        @cache
23
        def dp(i,j,c):
24
            if c==0:
25
                return 1 if pi[i][j]>0 else 0
26
            tmp=0
27
            for i1 in range(i+1,row):
28
                if pi[i][j]-pi[i1][j]!=0 and pi[i1][j]!=0:
29
                    tmp+=dp(i1,j,c-1)
30
                    tmp%=mod
31
            for j1 in range(j+1,col):
32
                if pi[i][j]-pi[i][j1]!=0 and pi[i][j1]!=0:
33
                    tmp+=dp(i,j1,c-1)
34
                    tmp%=mod
35
            return tmp
36
        return dp(0,0,k-1)%mod

灵神的刷题顺序:

动态规划:从记忆化搜索到递推

动态规划入门：从记忆化搜索到递推【基础算法精讲 17】(参考视频)

198打家劫舍

leetcode链接

维护一个数组vec[i]表示从前i个房子中能获得的最大金额和

vec[i]=max(vec[i-2]+nums[i],vec[i-1])

如果选择偷当前第i间的,最优收益是偷前i-2间的收益加上本间的收益

如果不偷当前第i间,最优收益是偷前i-1间的收益

C++:


xxxxxxxxxx
21
1
class Solution {
2
public:
3
    int rob(vector<int>& nums) 
4
    {
5
        vector<int>vec(nums.size());
6
        //先处理边界情况,确保nums.size()>2
7
        if(nums.size()==1)
8
            return nums[0];
9
        else if(nums.size()==2)
10
            return max(nums[0],nums[1]);
11
        vec[0]=nums[0];
12
        vec[1]=max(nums[0],nums[1]);
13
        int ret=0;//维护vec[]数组中的最大值
14
        for(int i=2;i<nums.size();++i)
15
        {
16
            vec[i]=max(vec[i-1],vec[i-2]+nums[i]);
17
            ret=max(ret,vec[i]);
18
        }
19
        return ret;
20
    }
21
};

Python:


xxxxxxxxxx
15
1
class Solution:
2
    def rob(self, nums: List[int]) -> int:
3
        li=[]
4
        le=len(nums)
5
        if le==1:
6
            return nums[0]
7
        elif le==2:
8
            return max(nums[0],nums[1])
9
        li.append(nums[0])
10
        li.append(max(nums[0],nums[1]))
11
        i=2
12
        while i<le:
13
            li.append(max(li[i-1],li[i-2]+nums[i]))
14
            i+=1
15
        return li[le-1]

(灵神的递归做法)


xxxxxxxxxx
9
1
class Solution:  # 递归做法
2
    def rob(self, nums: List[int]) -> int:
3
        @(cache)
4
        def dfs(idx):
5
            if idx<0:
6
                return 0
7
            cur=max(dfs(idx-1),dfs(idx-2)+nums[idx])
8
            return cur
9
        return dfs(len(nums)-1)

JavaScript:


xxxxxxxxxx
15
1
/**
2
 * @param {number[]} nums
3
 * @return {number}
4
 */
5
var rob = function(nums) 
6
{
7
    if(nums.length==1)
8
        return nums[0];
9
    let dp=new Array();
10
    dp[0]=nums[0];
11
    dp[1]=Math.max(nums[0],nums[1]);
12
    for(let i=2;i<nums.length;++i)
13
        dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
14
    return Math.max(dp[nums.length-1],dp[nums.length-2]);
15
};

课后作业：

70. 爬楼梯

leetcode链接

用vec[i]表示到达第i级楼梯至少需要几步

一次可以跨1或2阶,故vec[i]=vec[i-1]+vec[i-2]


xxxxxxxxxx
27
1
int a[46];
2
int digui(int n)
3
{
4
    if(a[n]!=0)
5
        return a[n];
6
    else
7
    {
8
        a[n]=digui(n-1)+digui(n-2);
9
        return a[n];
10
    }
11
}
12
int climbStairs(int n)
13
{
14
    a[1]=1;
15
    a[2]=2;
16
    if(n==1) 
17
    {
18
        //a[1]=1;
19
        return 1;
20
    }
21
    if(n==2) 
22
    {
23
        //a[2]=2;
24
        return 2;
25
    }
26
    return digui(n);
27
}

python:


xxxxxxxxxx
10
1
class Solution:  # 等价于斐波那契数列
2
    def climbStairs(self, n: int) -> int:
3
        @cache
4
        def dfs(i):
5
            if i==1:
6
                return 1
7
            elif i==2:
8
                return 2
9
            return dfs(i-1)+dfs(i-2)
10
        return dfs(n)

746. 使用最小花费爬楼梯

leetcode链接

用数组li[k]表示到达第k级的最小花费

因为出发没有花费,li[0]=li[1]=0

li[k]=min(li[k-1]+cost[k-1],li[k-2]+cost[k-2])

python:


xxxxxxxxxx
8
1
class Solution:
2
    def minCostClimbingStairs(self, cost: List[int]) -> int:
3
        i=0
4
        le=len(cost)
5
        li=[0]*(le+1)
6
        for k in range(2,le+1):
7
            li[k]=min(li[k-1]+cost[k-1],li[k-2]+cost[k-2])
8
        return li[le]

2466.统计构造好字符串的方案数

leetcode链接

dfs[i]表示长度为i的字符串的好字符串数目

dfs[0]=1,dfs[k]=0(k<0)

dfs[i]=dfs[i-zero]+dfs[i-one]

$m=10^9+7$ 取余

C++:


xxxxxxxxxx
28
1
using ll=long long;
2
class Solution {
3
public:
4
    int countGoodStrings(int low, int high, int zero, int one) 
5
    {
6
        ll m=1000000007;
7
        vector<ll>dfs(high+1);
8
        for(int i=1;i<=high;++i)
9
        {
10
            if(i-zero==0)
11
                dfs[i]+=1;
12
            else if(i-zero>0)
13
                dfs[i]+=dfs[i-zero];
14
            if(i-one==0)
15
                dfs[i]+=1;
16
            else if(i-one>0)
17
                dfs[i]+=dfs[i-one];
18
            dfs[i]%=m;              
19
        }
20
        ll ret=0;
21
        for(int i=low;i<=high;++i)
22
        {
23
            ret+=dfs[i];
24
            ret%=m;
25
        }
26
        return ret;
27
    }
28
};

python:


xxxxxxxxxx
15
1
m=10**9+7
2
class Solution:
3
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
4
        @cache
5
        def dfs(i):
6
            if i<0:
7
                return 0
8
            elif i==0:
9
                return 1
10
            return dfs(i-zero)%m+dfs(i-one)%m
11
        ret=0
12
        for k in range(low,high+1):
13
            ret+=dfs(k)
14
            ret=ret%m
15
        return ret%(10**9+7)

213.打家劫舍 II

leetcode链接

本题和打家劫舍类似,可以套用上次的代码,因为首尾相接,从[0,n]间房获得的最大收益等价于

max{从[0,n-1]间房获得的最大收益,从[1,n]间房获得的最大收益}


xxxxxxxxxx
30
1
int rob1(int* nums, int numsSize)
2
{
3
    int first=0,second=0,max=0;
4
    for(int i=0;i<numsSize;++i)
5
    {
6
        if(i>=2)
7
        {
8
            int this=first+nums[i]>second?first+nums[i]:second;
9
            first=second;
10
            second=this;
11
        }
12
        else
13
        {
14
            if(i==0)
15
                first=nums[0];
16
            else
17
                second=nums[1]>nums[0]?nums[1]:nums[0];
18
        }
19
    }
20
    return first>second?first:second;
21
}
22

23
int rob(int* nums, int numsSize)
24
{
25
    if(numsSize==1)
26
        return nums[0];
27
    int ans1=rob1(nums,numsSize-1);
28
    int ans2=rob1(nums+1,numsSize-1);
29
    return ans1>ans2?ans1:ans2;
30
}

python:


xxxxxxxxxx
18
1
class Solution:
2
    def rob(self, nums: List[int]) -> int:
3
        le=len(nums)
4
        if(le==1):
5
            return nums[0]
6
        n1=nums[0:le-1]
7
        n2=nums[1:le]
8
        @cache
9
        def dfs1(i):
10
            if i<0:
11
                return 0
12
            return max(dfs1(i-1),dfs1(i-2)+n1[i])
13
        @cache
14
        def dfs2(i):
15
            if i<0:
16
                return 0
17
            return max(dfs2(i-1),dfs2(i-2)+n2[i])
18
        return max(dfs1(le-2),dfs2(le-2))

Javascript:


xxxxxxxxxx
26
1
/**
2
 * @param {number[]} nums
3
 * @return {number}
4
 */
5
var rob1 = function(nums) 
6
{
7
    if(nums.length==1)
8
        return nums[0];
9
    let dp=new Array();
10
    dp[0]=nums[0];
11
    dp[1]=Math.max(nums[0],nums[1]);
12
    for(let i=2;i<nums.length;++i)
13
        dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
14
    return Math.max(dp[nums.length-1],dp[nums.length-2]);
15
};
16
var rob = function(nums) 
17
{
18
    if(nums.length==1)
19
        return nums[0];
20
    var back=nums.pop();
21
    var ret1=rob1(nums);
22
    nums.push(back);
23
    nums.shift();
24
    var ret2=rob1(nums);
25
    return Math.max(ret1,ret2);
26
};

拆分类动态规划

343.整数拆分

leetcode链接

参考视频

解法1:动态规划

定义dp[i]是整数i拆分后相乘能得到的最大整数(i>=2)

dp[i]=max(j*(i-j),j*dp[i-j]) (1<=j<i)


xxxxxxxxxx
17
1
class Solution {
2
public:
3
    int integerBreak(int n) 
4
    {
5
        vector<int>dp(60,0);
6
        dp[1]=1;
7
        dp[2]=1;
8
        for(int i=3;i<=n;++i)
9
        {
10
            for(int j=1;j<=i/2;++j)
11
            {
12
                dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
13
            }
14
        }
15
        return dp[n];
16
    }
17
};

解法2: 数学

粘贴自讨论区:

If an optimal product contains a factorf >= 4, then you can replace it with factors2and f-2 without losing optimality, as 2*(f-2) = 2f-4 >= f. So you never need a factor greater than or equal to 4, meaning you only need factors 1, 2 and 3 (and 1 is of course wasteful and you'd only use it for n=2 and n=3, where it's needed).

For the rest I agree, 3*3 is simply better than2*2*2, so you'd never use 2more than twice.


xxxxxxxxxx
19
1
int integerBreak(int n)
2
{
3
    switch(n)
4
    {
5
        case 2:return 1;
6
        case 3:return 2;
7
        case 4:return 4;
8
    }
9
    int a=n/3;
10
    int b=n%3;
11
    int ret=0;
12
    if(b==2)
13
        ret=pow(3,a)*2;
14
    else if(b==1)
15
        ret=pow(3,a-1)*4;
16
    else
17
        ret=pow(3,a);
18
    return ret;
19
}

96.不同的二叉搜索树

leetcode链接

参考视频

C++: 数组动规


xxxxxxxxxx
18
1
class Solution {
2
public:
3
    int numTrees(int n) 
4
    {
5
        vector<int>dp(20,0);
6
        dp[0]=1;
7
        dp[1]=1;
8
        for(int i=2;i<=n;++i)
9
        {
10
            for(int j=0;j<i/2;++j)
11
                dp[i]+=dp[i-j-1]*dp[j];
12
            dp[i]*=2;
13
            if(i%2!=0)
14
                dp[i]+=dp[i/2]*dp[i/2];
15
        }
16
        return dp[n];
17
    }
18
};

python: 记忆化递归


xxxxxxxxxx
11
1
class Solution:
2
    def numTrees(self, n: int) -> int:
3
        @cache
4
        def dp(idx):
5
            if idx==0:
6
                return 1
7
            tmp=0
8
            for i in range(0,idx):
9
                tmp+=dp(i)*dp(idx-1-i)
10
            return tmp
11
        return dp(n)

0-1背包和完全背包

01背包：416. 分割等和子集 474. 一和零 494. 目标和 879. 盈利计划 1049. 最后一块石头的重量 II 1230. 抛掷硬币

完全背包：1449. 数位成本和为目标值的最大数字 322. 零钱兑换 518. 零钱兑换 II 279. 完全平方数

0-1背包完全背包基础算法精讲 18(视频链接)

494. 目标和(0-1背包)

leetcode链接

解法1. 回溯(暴力)解法:可以1952ms踩线通过

C++:


xxxxxxxxxx
28
1
class Solution {
2
public:
3
    int findTargetSumWays(vector<int>& nums, int target) 
4
    {
5
        int cnt=0,add=0,left=0;
6
        left=accumulate(nums.begin(),nums.end(),0);
7
        function<void(int idx)>dfs=[&](int idx)
8
        {
9
            if(abs(target-add)>left)
10
                return;
11
            if(idx==nums.size())
12
            {
13
                if(add==target)
14
                    ++cnt;
15
                return;
16
            }
17
            add+=nums[idx];
18
            left-=nums[idx];
19
            dfs(idx+1);
20
            add-=2*nums[idx];
21
            dfs(idx+1);
22
            add+=nums[idx];
23
            left+=nums[idx];
24
        };
25
        dfs(0);
26
        return cnt;
27
    }
28
};

解法2:灵神的0-1背包记忆递归模板

记忆递归模板

示例出自CSDN

有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：eg：number＝4，capacity＝8

i（物品编号）	1	2	3	4
w（体积）	2	3	4	5
v（价值）	3	4	5	6

上述例子的dp数组打印: (dfs(i,c)=max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i]))

dfs	2	3	4	5	6	7	8
-1	0	0	0	0	0	0	0
0	3	3	3	3	3	3	3
1	3	4	4	7	7	7	7
2	3	4	5	7	8	9	9
3	3	4	5	7	8	9	10

灵神0-1背包递归模板(python):


xxxxxxxxxx
28
1
from functools import cache
2

3

4
def zero_one_knapsack(capacity: int, w: list[int], v: list[int]):
5
    """
6
    灵神0-1背包模板
7
    :param capacity: 背包容量
8
    :param w: 物品重量
9
    :param v: 物品价值
10
    :return: 取物品的最大价值
11
    """
12
    n = len(w)
13

14
    @cache
15
    def dfs(i, c):
16
        """
17
        深度优先搜索
18
        :param i: 只考虑前i件物品
19
        :param c: 剩余容量为c
20
        :return: 能获得的最大价值
21
        """
22
        if i < 0:
23
            return 0
24
        if c - w[i] < 0:
25
            return dfs(i - 1, c)
26
        return max(dfs(i - 1, c), dfs(i - 1, c - w[i]) + v[i])
27

28
    return dfs(n - 1, capacity)

上述模板的C++版本：


xxxxxxxxxx
33
1
#include<iostream>
2
#include<vector>
3
#include<unordered_map>
4
#include<functional>
5
#include<string>
6
using namespace std;
7
int zero_one_knapsack(int capacity,vector<int>&w,vector<int>&v)
8
{
9
    unordered_map<string,int>cache;//用于实现记忆化递归的哈希函数
10
    function<int(int,int)>dfs;
11
    function<int(int,int)>cdfs=[&](int i,int c)//直接可以调用，带有记忆化效果
12
    {
13
        string key=to_string(i)+string(",")+to_string(c);
14
        if(cache.find(key)==cache.end())
15
            cache[key]=dfs(i,c);
16
        return cache[key];
17
    };
18
    dfs=[&](int i,int c)
19
    {
20
        if(i<0)
21
            return 0;
22
        if(c-w[i]<0)
23
            return cdfs(i-1,c);
24
        return max(cdfs(i-1,c),cdfs(i-1,c-w[i])+v[i]);
25
    };
26
    // for(int i=-1;i<(int)w.size();++i)
27
    // {
28
    //     for(int j=0;j<=capacity;++j)
29
    //         cout<<cdfs(i,j)<<' ';
30
    //     cout<<endl;
31
    // }
32
    return cdfs(w.size()-1,capacity);
33
}

本题需要对上述模板进行变形,变形方式如下图

解题

python:


xxxxxxxxxx
17
1
class Solution:
2
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
3
        n=len(nums)
4
        add=0
5
        for k in nums:
6
            add+=k
7
        if add-target<0 or (add-target)%2==1:
8
            return 0
9
        add=(add-target)//2
10
        @cache
11
        def dfs(i:int,c:int):
12
            if i<0:
13
                return 1 if c==0 else 0
14
            if c<nums[i]:
15
                return dfs(i-1,c)
16
            return dfs(i-1,c)+dfs(i-1,c-nums[i])
17
        return dfs(n-1,add)

C++:


xxxxxxxxxx
30
1
class Solution {
2
public:
3
    int findTargetSumWays(vector<int>& nums, int target) 
4
    {
5
        int sum=accumulate(nums.begin(),nums.end(),0);
6
        if(sum<target||(sum-target)%2!=0)
7
            return 0;
8
        sum=(sum-target)/2;
9
        //核心代码模板
10
        unordered_map<string,int>cache;
11
        function<int(int,int)>dfs;
12
        function<int(int,int)>cdfs=[&](int i,int c)
13
        {
14
            string key=to_string(i)+string(",")+to_string(c);
15
            if(cache.find(key)==cache.end())
16
                cache[key]=dfs(i,c);
17
            return cache[key];
18
        };
19
        dfs=[&](int i,int c)
20
        {
21
            if(i<0)
22
                return c==0?1:0;
23
            if(c-nums[i]<0)
24
                return cdfs(i-1,c);
25
            return cdfs(i-1,c)+cdfs(i-1,c-nums[i]);
26
        };
27
        //
28
        return cdfs(nums.size()-1,sum);
29
    }
30
};

解法3: 数组递推的动态规划解法

本题相当于v[i]=1,w[i]=nums[i]的情况

$s=(\sum\limits_{i=0}^nnums[i])-target$

nums $\frac s 2$ ,求任意取几个数相加的方法总数

例如nums=[1,2,3,1,2],target=-1

只需在nums中任意取几个数相加,满足和等于5

`arr[i][j]`	0	1	2	3	4	5
-1	1	0	0	0	0	0
0(1)	1	1	0	0	0	0
1(2)	1	1	1	1	0	0
2(3)	1	1	1	2	1	1
3(1)	1	2	2	3	3	2
4(2)	1	2	3	5	5	5

arr[i][j]表示只考虑nums前i个元素时,相加得到j的最多方法数

arr[i][j]=arr[i-1][j]+arr[i-1][j-nums[i]]

注意坑: s为奇数或s<0都应当返回0

C++:


xxxxxxxxxx
23
1
class Solution {
2
public:
3
    int findTargetSumWays(vector<int>& nums, int target) 
4
    {
5
        int sum=accumulate(nums.begin(),nums.end(),0);
6
        int add=(sum-target)/2;
7
        if(sum-target<0||(sum-target)%2==1)
8
            return 0;
9
        vector<vector<int>>vec(nums.size()+1);
10
        for(auto& vec_:vec)
11
            vec_.resize(add+1);
12
        vec[0][0]=1;
13
        for(int i=1;i<=nums.size();++i)
14
        {
15
            int j=0;
16
            for(;j<nums[i-1]&&j<=add;++j)
17
                vec[i][j]=vec[i-1][j];
18
            for(;j<=add;++j)
19
                vec[i][j]=vec[i-1][j]+vec[i-1][j-nums[i-1]];
20
        }
21
        return vec[nums.size()][add];
22
    }
23
};

python:


xxxxxxxxxx
20
1
class Solution:
2
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
3
        add=0
4
        for k in nums:
5
            add+=k
6
        if (add-target)%2!=0 or add-target<0:
7
            return 0
8
        add=(add-target)//2
9
        size=len(nums)
10
        li = [0] * (size + 1)
11
        for k in range(size+1):
12
            li[k]=[0]*(add+1)
13
        li[0][0]=1
14
        for i in range(1,size+1):
15
            for j in range(add+1):
16
                if j-nums[i-1]>=0:
17
                    li[i][j]=li[i-1][j]+li[i-1][j-nums[i-1]]
18
                else:
19
                    li[i][j]=li[i-1][j]
20
        return li[size][add]

322. 零钱兑换

leetcode链接

这是一个完全背包问题

举例:


xxxxxxxxxx
2
1
输入：coins = [1, 2, 3, 4, 5], amount = 7
2
输出：3

arr[i][j]表示当前状态下所需最少硬币数

arr[i][j]=min(arr[i-1][j],arr[i][j-coins[i-1]]+1) $i\ge 1$ ）

`i`	coins	1	2	3	4	5	6	7
0		$\infin$	$\infin$	$\infin$	$\infin$	$\infin$	$\infin$	$\infin$
1	1	1	2	3	4	5	6	7
2	2	1	1	2	2	3	3	4
3	3	1	1	1	2	2	2	3
4	4	1	1	1	1	2	2	2
5	5	1	1	1	1	1	2	2

C++:二维数组递推


xxxxxxxxxx
21
1
#define big 0x7ffffff0 
2
class Solution {
3
public:
4
    int coinChange(vector<int>& coins, int amount) 
5
    {
6
        vector<vector<int>>vec(coins.size()+1);
7
        vec[0].resize(amount+1,big);
8
        vec[0][0]=0;
9
        for(int i=1;i<=coins.size();++i)
10
            vec[i].resize(amount+1);
11
        for(int i=1;i<=coins.size();++i)
12
        {
13
            int j=0;
14
            for(;j<coins[i-1]&&j<=amount;++j)
15
                vec[i][j]=vec[i-1][j];
16
            for(;j<=amount;++j)
17
                vec[i][j]=min(vec[i-1][j],vec[i][j-coins[i-1]]+1);
18
        }
19
        return vec[coins.size()][amount]==big?-1:vec[coins.size()][amount];
20
    }
21
};

Python:(记忆化递归)


xxxxxxxxxx
15
1
class Solution:
2
    def coinChange(self, coins: List[int], amount: int) -> int:
3
        n=len(coins)
4
        @cache
5
        def dfs(i,c):
6
            if c==0:
7
                return 0
8
            if i<0 or c<0:
9
                return inf
10
            return min(dfs(i-1,c),dfs(i,c-coins[i])+1)
11
        ret=dfs(n-1,amount)
12
        if ret==inf:
13
            return -1
14
        else:
15
            return ret

优化：压缩为一维数组

C++


xxxxxxxxxx
13
1
#define big 0x7ffffff0
2
class Solution {
3
public:
4
    int coinChange(vector<int>& coins, int amount) 
5
    {
6
        vector<int> vec(amount+1,big);
7
        vec[0]=0;
8
        for(int& coi:coins)
9
            for(int i=coi;i<=amount;++i)
10
                vec[i]=min(vec[i],vec[i-coi]+1);
11
        return vec[amount]==big?-1:vec[amount];
12
    }
13
};

python:


xxxxxxxxxx
11
1
class Solution:
2
    def coinChange(self, coins: List[int], amount: int) -> int:
3
        arr=[inf]*(amount+1)
4
        arr[0]=0
5
        for idx,coin in enumerate(coins):
6
            for i in range(coin,amount+1):
7
                arr[i]=min(arr[i],arr[i-coin]+1)
8
        if arr[amount]==inf:
9
            return -1
10
        else:
11
            return arr[amount]

课后作业：

416. 分割等和子集

leetcode链接

对于nums=[1,5,11,5]的测试用例

	0	1	5	6	10	11
	1	0	0	0	0	0
1	1	1	0	0	0	0
5	1	1	1	1	0	0
11	1	1	1	1	0	1
5	1	1	2	2	1	2

arr(i,c)=arr(i-1,c-num[i])+arr(i-1,c)

完成第5行时最后一列非0,可以返回True

记忆化递归

python:


xxxxxxxxxx
19
1
class Solution:
2
    def canPartition(self, nums: List[int]) -> bool:
3
        s=sum(nums)
4
        if s%2==1:
5
            return False
6
        s//=2
7
        @cache
8
        def dfs(i,c):
9
            if c==0:
10
                return 1
11
            if i<0:
12
                return 0
13
            if c-nums[i]<0:
14
                return dfs(i-1,c)
15
            return dfs(i-1,c-nums[i])+dfs(i-1,c)
16
        for k in range(len(nums)):  # k从小到大进行枚举
17
            if(dfs(k,s)!=0):
18
                return True
19
        return False

代码中k从小到大进行枚举,相当于按照nums数组由短到长枚举,很多数组只考虑前面一小段就符合条件,这样可以减少递归层级,防止超出内存限制

正常的二维数组动规:

C++:


xxxxxxxxxx
36
1
class Solution {
2
public:
3
    bool canPartition(vector<int>& nums) 
4
    {
5
        int sum=accumulate(nums.begin(),nums.end(),0);
6
        if(sum%2==1)
7
            return false;
8
        sum/=2;
9
        int m=nums.size();
10
        int n=sum;
11
        vector<vector<int>>arr(m+1);
12
        for(auto& ar:arr)
13
            ar.resize(n+1);
14
        int flag=0;
15
        for(int i=1;i<=m;++i)
16
        {
17
            for(int j=1;j<=n;++j)
18
            {
19
                if(j>=nums[i-1])
20
                    arr[i][j]=max(arr[i-1][j],arr[i-1][j-nums[i-1]]+nums[i-1]);
21
                else
22
                    arr[i][j]=arr[i-1][j];
23
                if(arr[i][j]==sum)
24
                {
25
                    flag=1;
26
                    goto Theend;
27
                }
28
            }
29
        }
30
        Theend:
31
        if(flag==1)
32
            return true;
33
        else
34
            return false;
35
    }
36
};

Javascript:


xxxxxxxxxx
31
1
/**
2
 * @param {number[]} nums
3
 * @return {boolean}
4
 */
5
var canPartition = function(nums) 
6
{
7
    let sum=eval(nums.join('+'));
8
    if(sum%2!=0)
9
        return false;
10
    sum/=2;
11
    len=nums.length;
12
    let arr=new Array();
13
    arr[0]=new Array();
14
    arr[0][0]=1;
15
    for(let j=1;j<=sum;++j)
16
        arr[0][j]=0;
17
    for(let i=1;i<=len;++i)
18
    {
19
        arr[i]=new Array();
20
        for(let j=0;j<=sum;++j)
21
        {
22
            if(j-nums[i-1]<0)
23
                arr[i][j]=arr[i-1][j];
24
            else
25
                arr[i][j]=arr[i-1][j]+arr[i-1][j-nums[i-1]];
26
        }
27
        if(arr[i][sum]>0)
28
            return true;
29
    }
30
    return false;
31
};

压缩为一维数组:

Python:使用临时数组


xxxxxxxxxx
16
1
class Solution:
2
    def canPartition(self, nums: List[int]) -> bool:
3
        s=sum(nums)
4
        if s%2!=0:
5
            return False
6
        s//=2
7
        arr=[0]*(s+1)
8
        arr[0]=1
9
        for idx,num in enumerate(nums):
10
            arr2=arr.copy()  # 注意:这里要用.copy(),否则会深拷贝
11
            for i in range(num,s+1):
12
                arr2[i]+=arr[i-num]
13
            if arr2[s]!=0:
14
                return True
15
            arr=arr2.copy()
16
        return False

C++:carl模板的倒序递推


xxxxxxxxxx
22
1
class Solution {
2
public:
3
    bool canPartition(vector<int>& nums) 
4
    {
5
        int sum=accumulate(nums.begin(),nums.end(),0);
6
        if(sum%2!=0)
7
            return false;
8
        sum/=2;
9
        cout<<sum<<endl;
10
        vector<int>dp(sum+1);
11
        for(int i=0;i<nums.size();++i)
12
        {
13
            for(int j=sum;j>=nums[i];--j)//从后往前遍历，就是0-1背包
14
            {
15
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);  
16
            }
17
            if(dp[sum]==sum)
18
                return true;
19
        }
20
        return false;
21
    }
22
};

注意：本题如果用C++，只能用递推公式dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);

而不能用dp[j]+=dp[j-nums[i]]，因为后者dp[i]的含义是当前枚举到的数中加和为i的所有组合总数，会溢出

分割等和子集问题的变换:

1049.最后一块石头的重量II

leetcode链接

$stones=[a_1,a_2,\cdots,a_n]$

$[b_1,b_2,\cdots,b_i]$ $[c_1,c_2,\cdots,c_j]$ $s$

$b_1+b_2+\cdots+b_i=c_1+c_2+\cdots+c_j+s$

$b_1,b_2,\cdots,b_i,c_1,c_2,\cdots,c_j\in stones$ )

$s$ 就是最后石头的最小可能重量

最后会把石头分成两堆，重量分别为add和su-add(add<=su-add)

add的理论最大值为su//add(//是整除)，只需让add从su//add开始枚举递减，直到找到一种石头组合是部分总重量为add

对应的最后一块石头的重量为su-add-add=su-2*add

python:


xxxxxxxxxx
17
1
class Solution:
2
    def lastStoneWeightII(self, stones: List[int]) -> int:
3
        su=sum(stones)
4
        le=len(stones)
5
        add=su//2
6
        @cache
7
        def dfs(i,c):
8
            if c==0:
9
                return 1
10
            if i<0:
11
                return 0
12
            if(c<stones[i]):
13
                return dfs(i-1,c)
14
            return dfs(i-1,c)+dfs(i-1,c-stones[i])
15
        while dfs(le-1,add)==0:
16
            add-=1
17
        return abs(su-2*add)

C++:


xxxxxxxxxx
32
1
#define mul 100000
2
class Solution {
3
public:
4
    int lastStoneWeightII(vector<int>& stones) 
5
    {
6
        int su=accumulate(stones.begin(),stones.end(),0);
7
        int le=stones.size();
8
        int add=su/2;
9
        unordered_map<int,int>cache;
10
        function<int(int,int)>dfs;
11
        function<int(int,int)>cdfs=[&](int i,int c)
12
        {
13
            int key=i*mul+c;
14
            if(cache.find(key)==cache.end())
15
                cache[key]=dfs(i,c);
16
            return cache[key];
17
        };
18
        dfs=[&](int i,int c)
19
        {
20
            if(c==0)
21
                return 1;
22
            if(i<0)
23
                return 0;
24
            if(c-stones[i]<0)
25
                return cdfs(i-1,c);
26
            return cdfs(i-1,c)+cdfs(i-1,c-stones[i]);
27
        };
28
        while(cdfs(le-1,add)==0)
29
            --add;
30
        return su-2*add;
31
    }
32
};

279. 完全平方数

leetcode链接

测试用例n=12:

arr=[1,4,9]

`dfs`	1	2	3	4	5	6	7	8	9	10	11	12
	$\infin$	$\infin$	$\infin$	$\infin$	$\infin$	$\infin$	$\infin$	$\infin$	$\infin$	$\infin$	$\infin$	$\infin$
1	1	2	3	4	5	6	7	8	9	10	11	12
4	1	2	3	1	2	3	4	2	3	4	5	3
9	1	2	3	1	2	3	4	2	1	2	3	3

dfs(i,c)=min(dfs(i-1,c),dfs(i,c-arr[i])+1)

递归会爆内存,所以只贴压缩为一维数组的递推代码

C++:


xxxxxxxxxx
14
1
class Solution {
2
public:
3
    int numSquares(int n) 
4
    {
5
        vector<int> arr(n+1);
6
        int g=0;
7
        generate(arr.begin(),arr.end(),[&](){return g++;});
8
        for(int i=2;i*i<=n;++i)
9
            for(int j=1;j<=n;++j)
10
                if(j-i*i>=0)
11
                    arr[j]=min(arr[j],arr[j-i*i]+1);
12
        return arr[n];
13
    }
14
};

python:


xxxxxxxxxx
13
1
class Solution:
2
    def numSquares(self, n: int) -> int:
3
        arr=[1]
4
        num=1
5
        while arr[num-1]<=n:
6
            num+=1
7
            arr.append(num**2)
8
        dfs=[inf]*(n+1)
9
        dfs[0]=0
10
        for idx,nu in enumerate(arr):
11
            for i in range(nu,n+1):
12
                dfs[i]=min(dfs[i],dfs[i-nu]+1)
13
        return dfs[n]

518. 零钱兑换 II

leetcode链接

	0	1	2	3	4	5
	1	0	0	0	0	0
1	1	1	1	1	1	1
2	1	1	2	2	3	3
5	1	1	2	2	3	4

vec[i][j]=vec[i-1][j]+vec[i][j-coins[i-1]];

二维数组法

C++:


xxxxxxxxxx
20
1
class Solution {
2
public:
3
    int change(int amount, vector<int>& coins) 
4
    {
5
        vector<vector<int>>vec(coins.size()+1);
6
        vec[0].resize(amount+1);
7
        for(int i=1;i<=coins.size();++i)
8
            vec[i].resize(amount+1);
9
        vec[0][0]=1;
10
        for(int i=1;i<=coins.size();++i)
11
        {
12
            int j=0;
13
            for(;j<coins[i-1]&&j<=amount;++j)
14
                vec[i][j]=vec[i-1][j];
15
            for(;j<=amount;++j)
16
                vec[i][j]=vec[i-1][j]+vec[i][j-coins[i-1]];
17
        }
18
        return vec[coins.size()][amount];
19
    }
20
};

(记忆化)递归法

python:


xxxxxxxxxx
13
1
class Solution:
2
    def change(self, amount: int, coins: List[int]) -> int:  # 灵神记忆化递归模板
3
        n=len(coins)
4
        @cache
5
        def dfs(i,c):
6
            if c==0:
7
                return 1
8
            if i<0:
9
                return 0
10
            if c-coins[i]<0:
11
                return dfs(i-1,c)
12
            return dfs(i-1,c)+dfs(i,c-coins[i])
13
        return dfs(n-1,amount)

压缩为一维数组:

C++:


xxxxxxxxxx
12
1
class Solution {
2
public:
3
    int change(int amount, vector<int>& coins) 
4
    {
5
        vector<int>arr(amount+1,0);
6
        arr[0]=1;
7
        for(int& coin:coins)
8
            for(int i=coin;i<=amount;++i)
9
                arr[i]+=arr[i-coin];
10
        return arr[amount];
11
    }
12
};

python:


xxxxxxxxxx
8
1
class Solution:
2
    def change(self, amount: int, coins: List[int]) -> int:
3
        arr=[0]*(amount+1)
4
        arr[0]=1
5
        for idx,coin in enumerate(coins):
6
            for i in range(coin,amount+1):
7
                arr[i]+=arr[i-coin]
8
        return arr[amount]

377.组合总和IV

leetcode链接

与上题几乎一样,区别使上一题求组合数,不考虑顺序,本题求排列数,考虑顺序

只需交换两个for循环的顺序

dp数组表：(nums=[1,2,3],target=4)

	0	1	2	3	4
	1	0	0	0	0
1	1	1	1	2	4
2	1	1	2	3	6
3	1	1	2	4	7

二维数组：

\begin{matrix} d p (i, c) = {\begin{cases} d p (i - 1, c), c < n u m s [i] \\ d p (i - 1, c) + d p (n u m s . s i z e () - 1, c - n u m s [i]), c \geq n u m s [i] \end{cases} \end{matrix}


xxxxxxxxxx
12
1
class Solution:
2
    def combinationSum4(self, nums: List[int], target: int) -> int:
3
        @cache
4
        def dfs(i,c):
5
            if c==0:
6
                return 1
7
            if i<0:
8
                return 0
9
            if c-nums[i]<0:
10
                return dfs(i-1,c)
11
            return dfs(len(nums)-1,c-nums[i])+dfs(i-1,c)
12
        return dfs(len(nums)-1,target)

一维数组：


xxxxxxxxxx
18
1
using ll=unsigned long long;
2
class Solution {
3
public:
4
    int combinationSum4(vector<int>& nums, int target) 
5
    {
6
        vector<ll>dp(target+1,0);
7
        dp[0]=1;
8
        for(int j=1;j<=target;++j)
9
        {
10
            for(int i=0;i<nums.size();++i)
11
            {
12
                if(j-nums[i]>=0)
13
                    dp[j]+=dp[j-nums[i]];
14
            }
15
        }
16
        return dp[target];
17
    }
18
};

474. 一和零

leetcode链接

这是一个0-1背包问题,区别是背包容量是一个二维的情况,即要同时考虑0和1的容量

w0[i]表示str[i]含有0的个数

w1[i]表示str[i]含有1的个数

dfs(i,c,d)表示只考虑前i个字符串,0的剩余容量为c,1的剩余容量为d的情况下,字串的最大长度

dfs(i,c,d)=max{dfs(i-1,c,d),dfs(i-1,c-w0[i],d-w1[i])+1}

方法1：灵神模板记忆化递归

python:


xxxxxxxxxx
16
1
class Solution:
2
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
3
        le=len(strs)
4
        w0=[0]*le
5
        w1=[0]*le
6
        for idx,s in enumerate(strs):
7
            w0[idx]=s.count("0")
8
            w1[idx]=s.count("1")
9
        @cache
10
        def dfs(i,c,d):
11
            if i<0:
12
                return 0
13
            if c<w0[i] or d<w1[i]:
14
                return dfs(i-1,c,d)
15
            return max(dfs(i-1,c,d),dfs(i-1,c-w0[i],d-w1[i])+1)
16
        return dfs(le-1,m,n)

C++:


xxxxxxxxxx
34
1
#define m1 (101*101)
2
#define m2 101
3
class Solution {
4
public:
5
    int findMaxForm(vector<string>& strs, int m, int n) 
6
    {
7
        int le=strs.size();
8
        vector<int>w0=vector<int>(le);
9
        vector<int>w1=vector<int>(le);
10
        for(int i=0;i<strs.size();++i)
11
        {
12
            w0[i]=count(strs[i].begin(),strs[i].end(),'0');
13
            w1[i]=count(strs[i].begin(),strs[i].end(),'1');
14
        }
15
        unordered_map<int,int>cache;
16
        function<int(int,int,int)>dfs;
17
        function<int(int,int,int)>cdfs=[&](int i,int n0,int n1)
18
        {
19
            int key=i*m1+n0*m2+n1;
20
            if(cache.find(key)==cache.end())
21
                cache[key]=dfs(i,n0,n1);
22
            return cache[key];
23
        };
24
        dfs=[&](int i,int n0,int n1)
25
        {
26
            if(i<0)
27
                return 0;
28
            if(n0-w0[i]<0||n1-w1[i]<0)
29
                return cdfs(i-1,n0,n1);
30
            return max(cdfs(i-1,n0,n1),cdfs(i-1,n0-w0[i],n1-w1[i])+1);
31
        };
32
        return cdfs(le-1,m,n);
33
    }
34
};

方法2：三维数组动规

C++:


xxxxxxxxxx
45
1
class Solution {
2
public:
3
    int findMaxForm(vector<string>& strs, int m, int n) 
4
    {
5
        int len=strs.size();
6
        vector<int>w0(len);
7
        vector<int>w1(len);
8
        for(int i=0;i<len;++i)
9
        {
10
            w0[i]=count(strs[i].begin(),strs[i].end(),'0');
11
            w1[i]=count(strs[i].begin(),strs[i].end(),'1');
12
        }
13
        vector<vector<vector<int>>> vec(len);
14
        for(auto& vec_1:vec)
15
        {
16
            vec_1.resize(m+1);
17
            for(auto& vec_2:vec_1)
18
                vec_2.resize(n+1);
19
        }
20
        for(int i=0;i<len;++i)
21
        {
22
            for(int j=0;j<=m;++j)
23
            {
24
                for(int k=0;k<=n;++k)
25
                {
26
                    if(i==0)
27
                    {
28
                        if(j<w0[i]||k<w1[i])
29
                            vec[i][j][k]=0;
30
                        else 
31
                            vec[i][j][k]=1;
32
                        continue;
33
                    }
34
                    if(j-w0[i]<0||k-w1[i]<0)
35
                    {
36
                        vec[i][j][k]=vec[i-1][j][k];
37
                        continue;
38
                    }
39
                    vec[i][j][k]=max(vec[i-1][j][k],vec[i-1][j-w0[i]][k-w1[i]]+1);
40
                }
41
            }
42
        }
43
        return vec[len-1][m][n];
44
    }
45
};

879.盈利计划

leetcode链接


xxxxxxxxxx
27
1
class Solution:
2
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
3
        m=10**9+7
4
        le=len(group)
5
        # 首先计算符合人数要求的所有方案
6
        @cache
7
        def dp1(i,num):
8
            if i<0:
9
                return 1
10
            if num-group[i]<0:
11
                return dp1(i-1,num)
12
            return (dp1(i-1,num)+dp1(i-1,num-group[i]))%m
13
        ans1=dp1(le-1,n)
14
        # 然后计算利润小于minProfit的方案
15
        @cache
16
        def dp2(i,g,p):
17
            if i==-1:
18
                return 1 if p==0 else 0
19
            if g-group[i]<0 or p-profit[i]<0:
20
                return dp2(i-1,g,p)%m
21
            return (dp2(i-1,g-group[i],p-profit[i])+dp2(i-1,g,p))%m
22
        maxprofit=sum(profit)
23
        ans2=0
24
        for i in range(minProfit):
25
            ans2+=dp2(len(group)-1,n,i)
26
            ans2%=m
27
        return (ans1+m-ans2)%m

最长公共子序列

最长公共子序列编辑距离【基础算法精讲 19】 (参考视频)

1143.最长公共子序列

leetcode链接

可以得到递推式：

可以证明，简化后结果为

\begin{matrix} d f s (i, j) = {\begin{cases} d f s (i - 1, j - 1) + 1 (s [i] = t [j]) \\ m a x {d f s (i - 1, j), d f s (i, j - 1)} (s [i] \neq t [j]) \end{cases} \end{matrix}

python:


xxxxxxxxxx
14
1
class Solution:
2
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
3
        m=len(text1)
4
        n=len(text2)
5
        arr=[[]]*(m+1)
6
        for idx,arr_ in enumerate(arr):
7
            arr[idx]=[0]*(n+1)
8
        for i in range(1,m+1):
9
            for j in range(1,n+1):
10
                if text1[i-1]==text2[j-1]:
11
                    arr[i][j]=arr[i-1][j-1]+1
12
                else:
13
                    arr[i][j]=max(arr[i-1][j],arr[i][j-1])
14
        return arr[m][n]

72. 编辑距离

leetcode链接

\begin{matrix} d p (i, j) = {\begin{cases} m i n {d p (i - 1, j), d p (i, j - 1), d p (i - 1, j - 1)} + 1, w o r d 1 [i] \neq w o r d 2 [j] \\ d p (i - 1, j - 1), w o r d 1 [i] = w o r d 2 [j] \end{cases} \end{matrix}

dp(i,j)	$\varnothing$	r	o	s
$\varnothing$	0	1	2	3
h	1	1	2	3
o	2	2	1	2
r	3	2	2	2
s	4	3	3	2
e	5	4	4	3


xxxxxxxxxx
14
1
class Solution:
2
    def minDistance(self, word1: str, word2: str) -> int:
3
        @cache
4
        def dp(i,j):
5
            if i==-1 and j==-1:
6
                return 0
7
            if i==-1:
8
                return dp(i,j-1)+1
9
            if j==-1:
10
                return dp(i-1,j)+1
11
            if word1[i]==word2[j]:
12
                return dp(i-1,j-1)
13
            return min(dp(i-1,j),dp(i,j-1),dp(i-1,j-1))+1
14
        return dp(len(word1)-1,len(word2)-1)

课后作业：

583. 两个字符串的删除操作

leetcode链接

点击跳转

712. 两个字符串的最小ASCII删除和

leetcode链接

\begin{matrix} d p (i, j) = {\begin{cases} d p (i - 1, j - 1) + a s c i i (s 1 [i]), s 1 [i] = s 2 [j] \\ m a x {d p (i - 1, j), d p (i, j - 1)}, s 1 [i] \neq s 2 [i] \end{cases} \end{matrix}


xxxxxxxxxx
15
1
class Solution:
2
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
3
        @cache
4
        def dp(i,j):
5
            if i<0 or j<0:
6
                return 0
7
            if s1[i]!=s2[j]:
8
                return max(dp(i-1,j),dp(i,j-1))
9
            return dp(i-1,j-1)+ord(s1[i])
10
        add=0
11
        for ch in s1:
12
            add+=ord(ch)
13
        for ch in s2:
14
            add+=ord(ch)
15
        return add-2*dp(len(s1)-1,len(s2)-1)

1458. 两个子序列的最大点积

leetcode链接

	3	0	-6
	0	0	0
2	6	6	6
1	6	6	6
-2	6	6	18
5	15	15	18

d p (i, j) = m a x {d p (i - 1, j - 1) + n u m s 1 [i] * n u m s 2 [j], d p (i - 1, j), d p (i, j - 1)}


xxxxxxxxxx
20
1
class Solution:
2
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
3
        @cache
4
        def dp(i,j):  # 记忆化递归
5
            if i<0 or j<0:
6
                return 0
7
            return max(dp(i-1,j-1)+nums1[i]*nums2[j],dp(i-1,j),dp(i,j-1))
8
        ret=dp(len(nums1)-1,len(nums2)-1)
9
        if ret==0:  # ret==0可能是因为答案为负数，此时需要分别找出两个数组中绝对值最小的元素，并相乘
10
            min1=inf
11
            for n in nums1:
12
                if abs(n)<abs(min1):
13
                    min1=n
14
            min2=inf
15
            for n in nums2:
16
                if abs(n)<abs(min2):
17
                    min2=n
18
            return min1*min2
19
        else:
20
            return ret

97. 交错字符串

leetcode链接

三维dp


xxxxxxxxxx
10
1
class Solution:
2
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
3
        @cache
4
        def dp(i,j,k):
5
            if i==-1 and j==-1 and k==-1:
6
                return True
7
            elif k==-1:
8
                return False
9
            return i!=-1 and dp(i-1,j,k-1) and s1[i]==s3[k] or j!=-1 and dp(i,j-1,k-1) and s2[j]==s3[k]
10
        return dp(len(s1)-1,len(s2)-1,len(s3)-1)

单调栈1：每日温度

leetcode739

C++:


xxxxxxxxxx
21
1
class Solution {
2
public:
3
    vector<int> dailyTemperatures(vector<int>& temperatures) 
4
    {
5
        vector<int> vec=temperatures;
6
        int n=vec.size();
7
        stack<pair<int,int>> sta;
8
        vector<int>ret(n);
9
        for(int i=n-1;i>=0;--i)
10
        {
11
            while(!sta.empty()&&sta.top().first<=vec[i])
12
                sta.pop();
13
            if(sta.empty())
14
                ret[i]=0;
15
            else
16
                ret[i]=sta.top().second-i;
17
            sta.push(make_pair(vec[i],i));
18
        }
19
        return ret;
20
    }
21
};

python:


xxxxxxxxxx
10
1
class Solution:
2
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
3
        stack=[[inf,-1]]  # 单调栈，其中元素必须递减
4
        ret=[0]*len(temperatures)
5
        for idx,num in enumerate(temperatures):
6
            while stack[len(stack)-1][0]<num:
7
                ret[stack[len(stack)-1][1]]=idx-stack[len(stack)-1][1]
8
                stack.pop(len(stack)-1)
9
            stack.append([num,idx])
10
        return ret

单调栈2：下一个更大元素I

leetcode496

原理和上一题一样，时间复杂度为O(nums1.length + nums2.length)


xxxxxxxxxx
29
1
class Solution {
2
public:
3
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) 
4
    {
5
        unordered_map<int,int> hash;
6
        for(int i=0;i<nums2.size();++i)
7
        {
8
            hash[nums2[i]]=i;
9
        }
10
        stack<int> sta;
11
        vector<int>ans(nums2.size());
12
        for(int i=nums2.size()-1;i>=0;--i)
13
        {
14
            while(!sta.empty()&&sta.top()<=nums2[i])
15
                sta.pop();
16
            if(sta.empty())
17
                ans[i]=-1;
18
            else
19
                ans[i]=sta.top();
20
            sta.push(nums2[i]);
21
        }
22
        vector<int> ret(nums1.size());
23
        for(int i=0;i<nums1.size();++i)
24
        {
25
            ret[i]=ans[hash[nums1[i]]];
26
        }
27
        return ret;
28
    }
29
};

	0	1	5	6	10	11
	1	0	0	0	0	0
1	1	1	0	0	0	0
5	1	1	1	1	0	0
11	1	1	1	1	0	1
5	1	1	2	2	1	2

	0	1	5	6	10	11
	1	0	0	0	0	0
1	1	1	0	0	0	0
5	1	1	1	1	0	0
11	1	1	1	1	0	1
5	1	1	2	2	1	2

	0	1	5	6	10	11
	1	0	0	0	0	0
1	1	1	0	0	0	0
5	1	1	1	1	0	0
11	1	1	1	1	0	1
5	1	1	2	2	1	2